Submission #423594

#	Time	Username	Problem	Language	Result	Execution time	Memory
423594		patrikpavic2	Crossing (JOI21_crossing)	C++17	26 / 100	709 ms	17796 KiB

Main

#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

const int N = 2e5 + 500;
const int BS = 31337;
const int OFF = (1 << 18);

int pot[N], P_pot[N], sol[N];
int prop[2 * OFF], T[2 * OFF];
int A[N][3], ql[N], qr[N], qq[N];
map < int, int > dobar;

void precompute(){
	pot[0] = 1, P_pot[0] = 1;
	for(int i = 1;i < N;i++){
		pot[i] = pot[i - 1] * BS;
		P_pot[i] = pot[i] + P_pot[i - 1];
	}
}

int kod(char c){
	if(c == 'J') return 0;
	if(c == 'O') return 1;
	return 2;
}

void refresh(int i, int l, int r){
	if(prop[i] == -1) return;
	T[i] = (P_pot[r] - (l ? P_pot[l - 1] : 0)) * (prop[i] + 1);
	if(i < OFF){
		prop[2 * i] = prop[i];
		prop[2 * i + 1] = prop[i];
	}	
	prop[i] = -1;
}

void update(int i, int a, int b, int lo, int hi, int kog){
	refresh(i, a, b);
	if(lo <= a && b <= hi){
		prop[i] = kog; refresh(i, a, b);
		return;
	}
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi, kog);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, kog);
	T[i] = T[2 * i] + T[2 * i + 1];
}

int n, q;

int main(){
	memset(prop, -1, sizeof(prop));
	precompute();
	scanf("%d", &n);
	for(int j = 0;j < 3;j++){
		for(int i = 0;i < n;i++){
			char c; scanf(" %c", &c);
			A[i][j] = kod(c);
		}
	}
	for(int ka = 0;ka < 3;ka++){
		for(int kb = 0;kb < 3;kb++){
			for(int kc = 0;kc < 3;kc++){
				if((ka + kb + kc) % 3 != 1) continue;
				int cur = 0;
				for(int i = 0;i < n;i++){
					cur += pot[i] * ((ka * A[i][0] + kb * A[i][1] + kc * A[i][2]) % 3 + 1);
				}
				dobar[cur] = 1;
			}	
		}
	}
	scanf("%d", &q);
	for(int i = 0;i < n;i++){
		char tmp; scanf(" %c", &tmp);
		update(1, 0, OFF - 1, i, i, kod(tmp));
	}
	printf(dobar[T[1]] ? "Yes\n" : "No\n");
	for(int i = 0;i < q;i++){
		int l, r; char tmp; scanf("%d%d %c", &l, &r, &tmp);
		int k = kod(tmp);
		update(1, 0, OFF - 1, l - 1, r - 1, k);
		printf(dobar[T[1]] ? "Yes\n" : "No\n");
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~
Main.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   char tmp; scanf(" %c", &tmp);
      |             ~~~~~^~~~~~~~~~~~~
Main.cpp:83:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   int l, r; char tmp; scanf("%d%d %c", &l, &r, &tmp);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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