(cache)Submission #68073979 - Japan Registry Services (JPRS) Programming Contest 2025#2 (AtCoder Beginner Contest 415)

Contest Duration: 2025-07-19(Sat) 21:00 - 2025-07-19(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #68073979

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define KI_MAX (1 << 19) /* 524288 */
/* 各文字の範囲を管理：範囲set、点get */
struct ri_s {
  char c;
  int l, r; /* 両端を含む */
} rki[KI_MAX * 2 - 1];
char rki_valid[KI_MAX * 2 - 1];
void rki_set_i(int idx, int ss, int se, int qs, int qe, struct ri_s value) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    rki[idx] = value;
    rki_valid[idx] = 1;
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    /* 何もしない */
  } else {
    int sm = ss + (se - ss) / 2;
    if (rki_valid[idx]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define KI_MAX (1 << 19) /* 524288 */

/* 各文字の範囲を管理：範囲set、点get */

struct ri_s {
	char c;
	int l, r; /* 両端を含む */
} rki[KI_MAX * 2 - 1];
char rki_valid[KI_MAX * 2 - 1];

void rki_set_i(int idx, int ss, int se, int qs, int qe, struct ri_s value) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		rki[idx] = value;
		rki_valid[idx] = 1;
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		if (rki_valid[idx]) {
			rki[idx * 2 + 1] = rki[idx * 2 + 2] = rki[idx];
			rki_valid[idx * 2 + 1] = rki_valid[idx * 2 + 2] = 1;
			rki_valid[idx] = 0;
		}
		rki_set_i(idx * 2 + 1, ss, sm, qs, qe, value);
		rki_set_i(idx * 2 + 2, sm, se, qs, qe, value);
	}
}

void rki_set(int qs, int qe, struct ri_s value) {
	rki_set_i(0, 0, KI_MAX, qs, qe, value);
}

struct ri_s rki_get_i(int idx, int ss, int se, int q) {
	if (rki_valid[idx]) {
		return rki[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		if (q < sm) {
			return rki_get_i(idx * 2 + 1, ss, sm, q);
		} else {
			return rki_get_i(idx * 2 + 2, sm, se, q);
		}
	}
}

struct ri_s rki_get(int q) {
	return rki_get_i(0, 0, KI_MAX, q);
}

/* 連続の最大長を管理：範囲set、範囲max */

int mki[KI_MAX * 2 - 1];
int mki_all[KI_MAX * 2 - 1];
char mki_all_valid[KI_MAX * 2 - 1];

int mki_set_i(int idx, int ss, int se, int qs, int qe, int value) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		mki_all[idx] = value;
		mki_all_valid[idx] = 1;
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		int l, r;
		if (mki_all_valid[idx]) {
			mki_all[idx * 2 + 1] = mki_all[idx * 2 + 2] = mki_all[idx];
			mki_all_valid[idx * 2 + 1] = mki_all_valid[idx * 2 + 2] = 1;
			mki_all_valid[idx] = 0;
		}
		l = mki_set_i(idx * 2 + 1, ss, sm, qs, qe, value);
		r = mki_set_i(idx * 2 + 2, sm, se, qs, qe, value);
		mki[idx] = l >= r ? l : r;
	}
	return mki_all_valid[idx] ? mki_all[idx] : mki[idx];
}

void mki_set(int qs, int qe, int value) {
	mki_set_i(0, 0, KI_MAX, qs, qe, value);
}

int mki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (se <= qs || qe <= ss) { /* 完全に外れている */
		return 0;
	} else if (mki_all_valid[idx]) { /* 全体に設定した値が生きている */
		return mki_all[idx];
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return mki[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		int l = mki_get_i(idx * 2 + 1, ss, sm, qs, qe);
		int r = mki_get_i(idx * 2 + 2, sm, se, qs, qe);
		return l >= r ? l : r;
	}
}

int mki_get(int qs, int qe) {
	return mki_get_i(0, 0, KI_MAX, qs, qe);
}

int N, Q;
char S[512345];
int Query[512345][3];

int main(void) {
	int i;
	int start;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	if (scanf("%512344s", S) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &Query[i][0], &Query[i][1]) != 2) return 1;
		if (Query[i][0] == 1) {
			char buf[4];
			if (scanf("%3s", buf) != 1) return 1;
			Query[i][2] = *buf;
		} else {
			if (scanf("%d", &Query[i][2]) != 1) return 1;
		}
	}
	/* i == N のとき、S[i] == '\0' のはずなので、番兵として活用する */
	for (i = 0, start = 0; i <= N; i++) {
		if (S[i] != S[start]) {
			/* 0-origin から 1-origin に変換する */
			rki_set(start + 1, i + 1, (struct ri_s){ S[start], start + 1, i });
			mki_set(start + 1, i + 1, i - start);
			start = i;
		}
	}
	for (i = 0; i < Q; i++) {
		if (Query[i][0] == 1) {
			struct ri_s cur = rki_get(Query[i][1]);
			/* 連続を切って新しい文字をセットする */
			if (cur.l < Query[i][1]) {
				rki_set(cur.l, Query[i][1], (struct ri_s){ cur.c, cur.l, Query[i][1] - 1 });
			}
			if (Query[i][1] < cur.r) {
				rki_set(Query[i][1] + 1, cur.r + 1, (struct ri_s){ cur.c, Query[i][1] + 1, cur.r });
			}
			rki_set(Query[i][1], Query[i][1] + 1, (struct ri_s){ (char)Query[i][2], Query[i][1], Query[i][1] });
			/* 隣と同じ文字なら、マージする */
			if (1 < Query[i][1]) {
				struct ri_s l = rki_get(Query[i][1] - 1);
				struct ri_s c = rki_get(Query[i][1]);
				if (l.c == c.c) {
					rki_set(l.l, c.r + 1, (struct ri_s){ l.c, l.l, c.r });
				}
			}
			if (Query[i][1] < N) {
				struct ri_s c = rki_get(Query[i][1]);
				struct ri_s r = rki_get(Query[i][1] + 1);
				if (c.c == r.c) {
					rki_set(c.l, r.r + 1, (struct ri_s){ c.c, c.l, r.r });
				}
			}
			/* 新しい連続数をセットする */
			cur = rki_get(Query[i][1]);
			mki_set(cur.l, cur.r + 1, cur.r - cur.l + 1);
			if (1 < Query[i][1] && cur.l == Query[i][1]) {
				struct ri_s left = rki_get(Query[i][1] - 1);
				mki_set(left.l, left.r + 1, left.r - left.l + 1);
			}
			if (Query[i][1] < N && cur.r == Query[i][1]) {
				struct ri_s right = rki_get(Query[i][1] + 1);
				mki_set(right.l, right.r + 1, right.r - right.l + 1);
			}
		} else if (Query[i][0] == 2) {
			struct ri_s left = rki_get(Query[i][1]);
			if (Query[i][2] <= left.r) {
				/* 指定された範囲は全て同じ文字 */
				printf("%d\n", Query[i][2] - Query[i][1] + 1);
			} else {
				/* 左端からの区間か、右端からの区間か、それ以外(あれば)か */
				struct ri_s right = rki_get(Query[i][2]);
				int ans = left.r - Query[i][1] + 1;
				int candidate = Query[i][2] - right.l + 1;
				if (candidate > ans) ans = candidate;
				if (left.r + 1 < right.l) {
					candidate = mki_get(left.r + 1, right.l);
					if (candidate > ans) ans = candidate;
				}
				printf("%d\n", ans);
			}
		}
	}
	return 0;
}

Submission Info

Submission Time	2025-08-01 08:04:26
Task	F - Max Combo
User	mikecat
Language	C (gcc 12.2.0)
Score	525
Code Size	5856 Byte
Status	AC
Exec Time	1049 ms
Memory	27916 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

525 / 525

Status

× 2

× 74

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt
All	evil_01.txt, evil_02.txt, evil_03.txt, evil_04.txt, evil_05.txt, evil_06.txt, evil_07.txt, evil_08.txt, evil_09.txt, evil_10.txt, evil_11.txt, evil_12.txt, evil_13.txt, evil_14.txt, evil_15.txt, evil_16.txt, evil_17.txt, evil_18.txt, evil_19.txt, evil_20.txt, evil_21.txt, evil_22.txt, evil_23.txt, evil_24.txt, evil_25.txt, evil_26.txt, evil_27.txt, evil_28.txt, sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt

Case Name	Status	Exec Time	Memory
evil_01.txt	AC	716 ms	23228 KiB
evil_02.txt	AC	770 ms	23184 KiB
evil_03.txt	AC	689 ms	23096 KiB
evil_04.txt	AC	759 ms	23212 KiB
evil_05.txt	AC	678 ms	25096 KiB
evil_06.txt	AC	729 ms	25188 KiB
evil_07.txt	AC	691 ms	25388 KiB
evil_08.txt	AC	772 ms	25332 KiB
evil_09.txt	AC	682 ms	25372 KiB
evil_10.txt	AC	740 ms	25348 KiB
evil_11.txt	AC	700 ms	25320 KiB
evil_12.txt	AC	766 ms	25452 KiB
evil_13.txt	AC	673 ms	26196 KiB
evil_14.txt	AC	716 ms	26128 KiB
evil_15.txt	AC	699 ms	26428 KiB
evil_16.txt	AC	743 ms	26428 KiB
evil_17.txt	AC	688 ms	26416 KiB
evil_18.txt	AC	727 ms	26560 KiB
evil_19.txt	AC	700 ms	26460 KiB
evil_20.txt	AC	749 ms	26552 KiB
evil_21.txt	AC	695 ms	27640 KiB
evil_22.txt	AC	716 ms	27652 KiB
evil_23.txt	AC	696 ms	27660 KiB
evil_24.txt	AC	718 ms	27512 KiB
evil_25.txt	AC	634 ms	27648 KiB
evil_26.txt	AC	630 ms	27532 KiB
evil_27.txt	AC	635 ms	27508 KiB
evil_28.txt	AC	674 ms	27516 KiB
sample_01.txt	AC	1 ms	1696 KiB
sample_02.txt	AC	0 ms	1628 KiB
test_01.txt	AC	834 ms	23264 KiB
test_02.txt	AC	870 ms	23332 KiB
test_03.txt	AC	860 ms	23340 KiB
test_04.txt	AC	835 ms	23320 KiB
test_05.txt	AC	839 ms	23444 KiB
test_06.txt	AC	835 ms	23488 KiB
test_07.txt	AC	819 ms	23464 KiB
test_08.txt	AC	830 ms	23524 KiB
test_09.txt	AC	818 ms	27352 KiB
test_10.txt	AC	834 ms	27428 KiB
test_11.txt	AC	829 ms	27612 KiB
test_12.txt	AC	828 ms	27776 KiB
test_13.txt	AC	812 ms	27328 KiB
test_14.txt	AC	806 ms	27436 KiB
test_15.txt	AC	794 ms	27432 KiB
test_16.txt	AC	818 ms	27424 KiB
test_17.txt	AC	828 ms	27340 KiB
test_18.txt	AC	834 ms	27452 KiB
test_19.txt	AC	262 ms	7360 KiB
test_20.txt	AC	263 ms	7544 KiB
test_21.txt	AC	250 ms	7724 KiB
test_22.txt	AC	255 ms	7740 KiB
test_23.txt	AC	203 ms	7988 KiB
test_24.txt	AC	204 ms	7816 KiB
test_25.txt	AC	117 ms	8316 KiB
test_26.txt	AC	123 ms	8452 KiB
test_27.txt	AC	114 ms	8248 KiB
test_28.txt	AC	119 ms	8456 KiB
test_29.txt	AC	113 ms	10588 KiB
test_30.txt	AC	107 ms	10500 KiB
test_31.txt	AC	731 ms	27852 KiB
test_32.txt	AC	733 ms	27916 KiB
test_33.txt	AC	730 ms	27716 KiB
test_34.txt	AC	734 ms	27764 KiB
test_35.txt	AC	748 ms	27740 KiB
test_36.txt	AC	731 ms	27816 KiB
test_37.txt	AC	738 ms	27596 KiB
test_38.txt	AC	746 ms	27596 KiB
test_39.txt	AC	761 ms	27536 KiB
test_40.txt	AC	756 ms	27740 KiB
test_41.txt	AC	809 ms	27496 KiB
test_42.txt	AC	802 ms	27512 KiB
test_43.txt	AC	1044 ms	23456 KiB
test_44.txt	AC	1049 ms	23468 KiB