oj.uz

Submission #514829

# Submission time Handle Problem Language Result Execution time Memory
514829 2022-01-18T14:32:58 Z ritul_kr_singh Game (IOI13_game) C++17
100 / 100
 3585 ms 233088 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
#define m ((l + r) / 2)
 
const int N = 6e5, M = 1.3e7, B = 25;
 
ll gcd2(ll X, ll Y) {
	while(X != Y && Y) swap(X %= Y, Y);
	return X;
}
 
int limRow, limCol, sL, sR; ll sV;
 
ll sGcd[M], xGcd[N*B];
int G[M], H[M], sCnt, xCnt, xP[N*B], xRow[N*B];
 
void sUpd(int l, int r, int u) {
	if(r - l < 2) return void(sGcd[u] = sV);
 
	sL<m? sUpd(l, m, G[u] ? : G[u] = ++sCnt):
		  sUpd(m, r, H[u] ? : H[u] = ++sCnt);
	sGcd[u] = gcd2(G[u] ? sGcd[G[u]] : 0LL, H[u] ? sGcd[H[u]] : 0LL);
}
 
ll sQry(int l, int r, int u) {
	if(sL<=l && r<=sR) return sGcd[u];
	if(sR<=l || r<=sL) return 0LL;
	return gcd2((G[u] ? sQry(l, m, G[u]) : 0LL),
				(H[u] ? sQry(m, r, H[u]) : 0LL));
}
 
void pointSet(int row, ll v, int &s) {
	if(s < 0) {	
		int i = -s, j = xP[i]; xP[i]++;
 
		for(int k=0; k+1<xP[i]; ++k) if(xRow[i+k] == row) {
			j = k; --xP[i];
			break;
		}
		xGcd[i+j] = v;
		xRow[i+j] = row;
 
		if(xP[i] == B) {
			s = ++sCnt;
 
			for(j=0; j<B; ++j)
				pointSet(xRow[i+j], xGcd[i+j], s);
		}
	} else sL = row, sV = v, sUpd(0, limRow, s);
}
 
ll rangeGcd(int l, int r, int &u) {
	if(u < 0) {
		int i = -u;
		ll res = 0;
		for(int j=0; j<xP[i]; ++j)
			if(l <= xRow[i+j] && xRow[i+j] < r)
				res = gcd2(res, xGcd[i+j]);
		return res;
	}
	sL = l, sR = r;
	return sQry(0, limRow, u);
}
 
int S[N], L[N], R[N], tL, tR, row, tCnt = 1;
ll currV;
 
void upd(int l, int r, int u) {
	if(!S[u]) (S[u] = --xCnt), xCnt -= B;
	if(r - l < 2) return pointSet(row, currV, S[u]);
 
	tL<m? upd(l, m, L[u] ? : L[u] = ++tCnt):
		  upd(m, r, R[u] ? : R[u] = ++tCnt);
 
	sV = gcd2(rangeGcd(row, row + 1, S[L[u]]),
			  rangeGcd(row, row + 1, S[R[u]]));
	pointSet(row, sV, S[u]);
}
 
ll query(int l, int r, int u) {
	if(tR<=l || r<=tL || !u || !S[u]) return 0LL;
	if(tL<=l && r<=tR) return rangeGcd(sL, sR, S[u]);
 
	return gcd2(query(l, m, L[u]), query(m, r, R[u]));
}
 
void init(int r, int c) { limCol = c, limRow = r; }
 
void update(int P, int Q, ll K) {
	row = P, tL = Q; currV = K;
	upd(0, limCol, 1);
}
 
ll calculate(int P, int Q, int U, int V) {
	sL = P, sR = U + 1;
	tL = Q, tR = V + 1;
    return query(0, limCol, 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 410 ms 24912 KB Output is correct
5 Correct 390 ms 25164 KB Output is correct
6 Correct 572 ms 21876 KB Output is correct
7 Correct 590 ms 21652 KB Output is correct
8 Correct 356 ms 14664 KB Output is correct
9 Correct 570 ms 21788 KB Output is correct
10 Correct 595 ms 21396 KB Output is correct
11 Correct 0 ms 296 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 304 KB Output is correct
12 Correct 753 ms 10356 KB Output is correct
13 Correct 1306 ms 4948 KB Output is correct
14 Correct 252 ms 2372 KB Output is correct
15 Correct 1531 ms 6268 KB Output is correct
16 Correct 181 ms 8936 KB Output is correct
17 Correct 605 ms 7148 KB Output is correct
18 Correct 916 ms 9196 KB Output is correct
19 Correct 872 ms 9456 KB Output is correct
20 Correct 883 ms 8840 KB Output is correct
21 Correct 0 ms 300 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 424 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 416 ms 25044 KB Output is correct
13 Correct 380 ms 25132 KB Output is correct
14 Correct 535 ms 21852 KB Output is correct
15 Correct 621 ms 21716 KB Output is correct
16 Correct 369 ms 14760 KB Output is correct
17 Correct 640 ms 21864 KB Output is correct
18 Correct 620 ms 21444 KB Output is correct
19 Correct 855 ms 10380 KB Output is correct
20 Correct 1272 ms 4932 KB Output is correct
21 Correct 252 ms 2440 KB Output is correct
22 Correct 1627 ms 6156 KB Output is correct
23 Correct 168 ms 9028 KB Output is correct
24 Correct 614 ms 6912 KB Output is correct
25 Correct 973 ms 9268 KB Output is correct
26 Correct 886 ms 9428 KB Output is correct
27 Correct 808 ms 8864 KB Output is correct
28 Correct 531 ms 102352 KB Output is correct
29 Correct 1364 ms 111188 KB Output is correct
30 Correct 2936 ms 91868 KB Output is correct
31 Correct 2650 ms 70816 KB Output is correct
32 Correct 324 ms 2556 KB Output is correct
33 Correct 546 ms 3656 KB Output is correct
34 Correct 307 ms 108596 KB Output is correct
35 Correct 866 ms 55940 KB Output is correct
36 Correct 1810 ms 108572 KB Output is correct
37 Correct 1484 ms 108840 KB Output is correct
38 Correct 1404 ms 108080 KB Output is correct
39 Correct 1151 ms 84540 KB Output is correct
40 Correct 0 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 392 ms 24836 KB Output is correct
13 Correct 363 ms 25040 KB Output is correct
14 Correct 510 ms 21876 KB Output is correct
15 Correct 589 ms 21676 KB Output is correct
16 Correct 391 ms 14712 KB Output is correct
17 Correct 585 ms 21828 KB Output is correct
18 Correct 545 ms 21400 KB Output is correct
19 Correct 733 ms 10436 KB Output is correct
20 Correct 1368 ms 4884 KB Output is correct
21 Correct 244 ms 2388 KB Output is correct
22 Correct 1555 ms 6324 KB Output is correct
23 Correct 172 ms 8980 KB Output is correct
24 Correct 617 ms 6888 KB Output is correct
25 Correct 947 ms 9188 KB Output is correct
26 Correct 855 ms 9488 KB Output is correct
27 Correct 850 ms 8988 KB Output is correct
28 Correct 684 ms 102436 KB Output is correct
29 Correct 1570 ms 111364 KB Output is correct
30 Correct 2945 ms 91900 KB Output is correct
31 Correct 2650 ms 70876 KB Output is correct
32 Correct 335 ms 2640 KB Output is correct
33 Correct 519 ms 3604 KB Output is correct
34 Correct 306 ms 108708 KB Output is correct
35 Correct 867 ms 56204 KB Output is correct
36 Correct 1760 ms 108864 KB Output is correct
37 Correct 1349 ms 109004 KB Output is correct
38 Correct 1392 ms 108208 KB Output is correct
39 Correct 709 ms 215200 KB Output is correct
40 Correct 1964 ms 233088 KB Output is correct
41 Correct 3585 ms 188268 KB Output is correct
42 Correct 3316 ms 144116 KB Output is correct
43 Correct 589 ms 231620 KB Output is correct
44 Correct 427 ms 2852 KB Output is correct
45 Correct 1189 ms 84712 KB Output is correct
46 Correct 2579 ms 232360 KB Output is correct
47 Correct 2530 ms 232336 KB Output is correct
48 Correct 2339 ms 232172 KB Output is correct
49 Correct 0 ms 300 KB Output is correct