Submission #423596

#	Time	Username	Problem	Language	Result	Execution time	Memory
423596		patrikpavic2	Crossing (JOI21_crossing)	C++17	100 / 100	670 ms	17812 KiB

Main

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

using namespace std;

typedef long long ll;

const int N = 2e5 + 500;
const int MOD = 1e9 + 7;
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];
map < int, int > dobar;

inline int add(int A, int B){
	if(A + B >= MOD)
		return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B){
	if(A - B < 0)
		return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

void precompute(){
	pot[0] = 1, P_pot[0] = 1;
	for(int i = 1;i < N;i++){
		pot[i] = mul(pot[i - 1], BS);
		P_pot[i] = add(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] = mul(sub(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] = add(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 = add(cur, mul(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:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~
Main.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   char tmp; scanf(" %c", &tmp);
      |             ~~~~~^~~~~~~~~~~~~
Main.cpp:102:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   int l, r; char tmp; scanf("%d%d %c", &l, &r, &tmp);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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