Submission #716344

#	Time	Username	Problem	Language	Result	Execution time	Memory
716344		rainboy	Crossing (JOI21_crossing)	C11	100 / 100	313 ms	22604 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define MD	0x7fffffff

char *joi = "JOI";

int X = 469762049, Y = 595591169;

int ppx[N + 1], ppy[N + 1];

void init() {
	int i;

	ppx[0] = ppy[0] = 1;
	for (i = 1; i <= N; i++) {
		ppx[i] = (long long) ppx[i - 1] * X % MD;
		ppy[i] = (long long) ppy[i - 1] * Y % MD;
	}
}

int xx_[N_ * 2], yy_[N_ * 2], xx1[N_ * 2][3], yy1[N_ * 2][3], lz[N_], h_, n_;

void put(int i, int d) {
	xx_[i] = xx1[i][d], yy_[i] = yy1[i][d];
	if (i < n_)
		lz[i] = d;
}

void pus(int i) {
	if (lz[i] != -1)
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -1;
}

void pul(int i) {
	if (lz[i] == -1) {
		int l = i << 1, r = l | 1;

		xx_[i] = ((long long) xx_[l] + xx_[r]) % MD;
		yy_[i] = ((long long) yy_[l] + yy_[r]) % MD;
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(char *cc, int n) {
	int i, l, r, d;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n; i++) {
		for (d = 0; d < 3; d++) {
			xx1[n_ + i][d] = (long long) d * ppx[i] % MD;
			yy1[n_ + i][d] = (long long) d * ppy[i] % MD;
		}
		xx_[n_ + i] = (long long) cc[i] * ppx[i] % MD;
		yy_[n_ + i] = (long long) cc[i] * ppy[i] % MD;
	}
	memset(lz, -1, n_ * sizeof *lz);
	for (i = n_ - 1; i > 0; i--) {
		l = i << 1, r = l | 1;
		for (d = 0; d < 3; d++) {
			xx1[i][d] = ((long long) xx1[l][d] + xx1[r][d]) % MD;
			yy1[i][d] = ((long long) yy1[l][d] + yy1[r][d]) % MD;
		}
		pul(i);
	}
}

void update(int l, int r, int d) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, d);
		if ((r & 1) == 0)
			put(r--, d);
	}
	pull(l_), pull(r_);
}

int main() {
	static char ss[3][N + 1], cc[N + 1];
	static int xx[3][3], yy[3][3];
	int n, q, h, i, a, b, c, d, x, y, yes;

	scanf("%d", &n), init();
	for (h = 0; h < 3; h++) {
		scanf("%s", ss[h]);
		for (i = 0; i < n; i++)
			ss[h][i] = strchr(joi, ss[h][i]) - joi;
	}
	for (a = 0; a < 3; a++)
		for (b = 0; b < 3; b++) {
			c = (4 - a - b) % 3;
			x = y = 0;
			for (i = 0; i < n; i++) {
				d = (ss[0][i] * a + ss[1][i] * b + ss[2][i] * c) % 3;
				x = (x + (long long) d * ppx[i]) % MD;
				y = (y + (long long) d * ppy[i]) % MD;
			}
			xx[a][b] = x, yy[a][b] = y;
		}
	scanf("%d%s", &q, cc);
	for (i = 0; i < n; i++)
		cc[i] = strchr(joi, cc[i]) - joi;
	build(cc, n);
	yes = 0;
	for (a = 0; a < 3; a++)
		for (b = 0; b < 3; b++)
			if (xx_[1] == xx[a][b] && yy_[1] == yy[a][b]) {
				yes = 1;
				goto out;
			}
out:
	printf(yes ? "Yes\n" : "No\n");
	while (q--) {
		static char s[2];
		int l, r;

		scanf("%d%d%s", &l, &r, s), l--, r--;
		d = strchr(joi, s[0]) - joi;
		update(l, r, d);
		yes = 0;
		for (a = 0; a < 3; a++)
			for (b = 0; b < 3; b++)
				if (xx_[1] == xx[a][b] && yy_[1] == yy[a][b]) {
					yes = 1;
					goto out_;
				}
out_:
		printf(yes ? "Yes\n" : "No\n");
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d", &n), init();
      |  ^~~~~~~~~~~~~~~
Main.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%s", ss[h]);
      |   ^~~~~~~~~~~~~~~~~~
Main.c:119:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  scanf("%d%s", &q, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:136:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   scanf("%d%d%s", &l, &r, s), l--, r--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51