oj.uz

Submission #423594

# Submission time Handle Problem Language Result Execution time Memory
423594 2021-06-11T10:02:06 Z patrikpavic2 Crossing (JOI21_crossing) C++17
26 / 100
 709 ms 17796 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 11528 KB Output is correct
2 Correct 220 ms 12132 KB Output is correct
3 Correct 197 ms 7260 KB Output is correct
4 Correct 245 ms 12124 KB Output is correct
5 Correct 253 ms 12160 KB Output is correct
6 Correct 201 ms 11540 KB Output is correct
7 Correct 230 ms 11892 KB Output is correct
8 Correct 324 ms 12408 KB Output is correct
9 Correct 280 ms 12068 KB Output is correct
10 Correct 347 ms 13116 KB Output is correct
11 Correct 229 ms 12540 KB Output is correct
12 Correct 258 ms 13224 KB Output is correct
13 Correct 233 ms 12540 KB Output is correct
14 Correct 260 ms 13332 KB Output is correct
15 Correct 268 ms 12544 KB Output is correct
16 Correct 249 ms 13192 KB Output is correct
17 Correct 294 ms 12580 KB Output is correct
18 Correct 165 ms 6016 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 11528 KB Output is correct
2 Correct 220 ms 12132 KB Output is correct
3 Correct 197 ms 7260 KB Output is correct
4 Correct 245 ms 12124 KB Output is correct
5 Correct 253 ms 12160 KB Output is correct
6 Correct 201 ms 11540 KB Output is correct
7 Correct 230 ms 11892 KB Output is correct
8 Correct 324 ms 12408 KB Output is correct
9 Correct 280 ms 12068 KB Output is correct
10 Correct 347 ms 13116 KB Output is correct
11 Correct 229 ms 12540 KB Output is correct
12 Correct 258 ms 13224 KB Output is correct
13 Correct 233 ms 12540 KB Output is correct
14 Correct 260 ms 13332 KB Output is correct
15 Correct 268 ms 12544 KB Output is correct
16 Correct 249 ms 13192 KB Output is correct
17 Correct 294 ms 12580 KB Output is correct
18 Correct 165 ms 6016 KB Output is correct
19 Correct 709 ms 15648 KB Output is correct
20 Correct 597 ms 16384 KB Output is correct
21 Correct 556 ms 16636 KB Output is correct
22 Correct 442 ms 14800 KB Output is correct
23 Correct 328 ms 14096 KB Output is correct
24 Correct 272 ms 13176 KB Output is correct
25 Correct 593 ms 17464 KB Output is correct
26 Correct 463 ms 15976 KB Output is correct
27 Correct 541 ms 17796 KB Output is correct
28 Correct 504 ms 15888 KB Output is correct
29 Correct 524 ms 17352 KB Output is correct
30 Correct 300 ms 14048 KB Output is correct
31 Correct 638 ms 17780 KB Output is correct
32 Correct 503 ms 15512 KB Output is correct
33 Correct 279 ms 13092 KB Output is correct
34 Correct 577 ms 16044 KB Output is correct
35 Correct 393 ms 15168 KB Output is correct
36 Correct 287 ms 13188 KB Output is correct
37 Correct 266 ms 13128 KB Output is correct
38 Correct 437 ms 14216 KB Output is correct
39 Correct 339 ms 13124 KB Output is correct
40 Incorrect 394 ms 14904 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 11528 KB Output is correct
2 Correct 220 ms 12132 KB Output is correct
3 Correct 197 ms 7260 KB Output is correct
4 Correct 245 ms 12124 KB Output is correct
5 Correct 253 ms 12160 KB Output is correct
6 Correct 201 ms 11540 KB Output is correct
7 Correct 230 ms 11892 KB Output is correct
8 Correct 324 ms 12408 KB Output is correct
9 Correct 280 ms 12068 KB Output is correct
10 Correct 347 ms 13116 KB Output is correct
11 Correct 229 ms 12540 KB Output is correct
12 Correct 258 ms 13224 KB Output is correct
13 Correct 233 ms 12540 KB Output is correct
14 Correct 260 ms 13332 KB Output is correct
15 Correct 268 ms 12544 KB Output is correct
16 Correct 249 ms 13192 KB Output is correct
17 Correct 294 ms 12580 KB Output is correct
18 Correct 165 ms 6016 KB Output is correct
19 Correct 223 ms 11736 KB Output is correct
20 Correct 187 ms 7288 KB Output is correct
21 Correct 231 ms 12740 KB Output is correct
22 Correct 187 ms 11296 KB Output is correct
23 Correct 261 ms 12792 KB Output is correct
24 Correct 266 ms 11972 KB Output is correct
25 Correct 284 ms 12636 KB Output is correct
26 Correct 254 ms 11780 KB Output is correct
27 Correct 219 ms 12740 KB Output is correct
28 Correct 228 ms 11884 KB Output is correct
29 Correct 226 ms 12328 KB Output is correct
30 Correct 210 ms 11492 KB Output is correct
31 Correct 225 ms 13092 KB Output is correct
32 Correct 224 ms 12796 KB Output is correct
33 Correct 226 ms 12404 KB Output is correct
34 Correct 220 ms 11860 KB Output is correct
35 Correct 232 ms 13188 KB Output is correct
36 Correct 214 ms 12636 KB Output is correct
37 Correct 268 ms 13232 KB Output is correct
38 Correct 256 ms 12564 KB Output is correct
39 Correct 223 ms 13252 KB Output is correct
40 Correct 237 ms 12712 KB Output is correct
41 Correct 221 ms 13176 KB Output is correct
42 Correct 242 ms 12636 KB Output is correct
43 Correct 226 ms 12176 KB Output is correct
44 Correct 214 ms 12380 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 11528 KB Output is correct
2 Correct 220 ms 12132 KB Output is correct
3 Correct 197 ms 7260 KB Output is correct
4 Correct 245 ms 12124 KB Output is correct
5 Correct 253 ms 12160 KB Output is correct
6 Correct 201 ms 11540 KB Output is correct
7 Correct 230 ms 11892 KB Output is correct
8 Correct 324 ms 12408 KB Output is correct
9 Correct 280 ms 12068 KB Output is correct
10 Correct 347 ms 13116 KB Output is correct
11 Correct 229 ms 12540 KB Output is correct
12 Correct 258 ms 13224 KB Output is correct
13 Correct 233 ms 12540 KB Output is correct
14 Correct 260 ms 13332 KB Output is correct
15 Correct 268 ms 12544 KB Output is correct
16 Correct 249 ms 13192 KB Output is correct
17 Correct 294 ms 12580 KB Output is correct
18 Correct 165 ms 6016 KB Output is correct
19 Correct 709 ms 15648 KB Output is correct
20 Correct 597 ms 16384 KB Output is correct
21 Correct 556 ms 16636 KB Output is correct
22 Correct 442 ms 14800 KB Output is correct
23 Correct 328 ms 14096 KB Output is correct
24 Correct 272 ms 13176 KB Output is correct
25 Correct 593 ms 17464 KB Output is correct
26 Correct 463 ms 15976 KB Output is correct
27 Correct 541 ms 17796 KB Output is correct
28 Correct 504 ms 15888 KB Output is correct
29 Correct 524 ms 17352 KB Output is correct
30 Correct 300 ms 14048 KB Output is correct
31 Correct 638 ms 17780 KB Output is correct
32 Correct 503 ms 15512 KB Output is correct
33 Correct 279 ms 13092 KB Output is correct
34 Correct 577 ms 16044 KB Output is correct
35 Correct 393 ms 15168 KB Output is correct
36 Correct 287 ms 13188 KB Output is correct
37 Correct 266 ms 13128 KB Output is correct
38 Correct 437 ms 14216 KB Output is correct
39 Correct 339 ms 13124 KB Output is correct
40 Incorrect 394 ms 14904 KB Output isn't correct
41 Halted 0 ms 0 KB -