oj.uz

Submission #396519

# Submission time Handle Problem Language Result Execution time Memory
396519 2021-04-30T06:26:56 Z phathnv Game (IOI13_game) C++17
100 / 100
 5091 ms 92928 KB 
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;
int sz1=1, sz2=1;
 
struct T { ll x; int p, l, r; } X[60000000];
struct seg {
	int N, root;
	seg(const int n) : N(n-1) { root=0; }
	ll get(int l, int r, int s, int e, int i) const {
		if(!i || e<l || r<s) return 0;
		if(l<=s && e<=r) return X[i].x;
		if(~X[i].p) return l<=X[i].p && X[i].p<=r ? X[i].x : 0;
		int m=(s+e)>>1;
		return gcd(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
	}
	ll get(int l, int r) const { return get(l, r, 0, N, root); }
	ll set(int p, ll x, int s, int e, int&i) {
		if(p<s || e<p) return X[i].x;
		if(!i) { X[i=sz1++]={x, p, 0, 0}; return x; }
		if(s==e) return X[i].x=x;
		int m=(s+e)>>1;
		if(~X[i].p) set(X[i].p, X[i].x, s, m, X[i].l), set(X[i].p, X[i].x, m+1, e, X[i].r), X[i].p=-1;
		return X[i].x=gcd(set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r));
	}
	void set(int p, ll x) { set(p, x, 0, N, root); }
};
 
struct T2 { seg* x; int l, r; } Y[4194304];
struct seg2 {
	int N, M, root;
	seg2(int n, int m) : N(n-1), M(m) { root=0; }
	ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
		if(!i || e<l1 || r1<s) return 0;
		if(l1<=s && e<=r1) return Y[i].x->get(l2, r2);
		int m=(s+e)>>1;
		return gcd(get(l1, r1, l2, r2, s, m, Y[i].l), get(l1, r1, l2, r2, m+1, e, Y[i].r));
	}
	ll get(int l1, int r1, int l2, int r2) const { return get(l1, r1, l2, r2, 0, N, root); }
	ll set(int p, int q, ll x, int s, int e, int&i) {
		if(p<s || e<p) return i ? Y[i].x->get(q, q) : 0;
		if(!i) Y[i=sz2++].x=new seg(M);
		if(s==e) {
			Y[i].x->set(q, x);
			return x;
		}
		int m=(s+e)>>1;
		ll y=gcd(set(p, q, x, s, m, Y[i].l), set(p, q, x, m+1, e, Y[i].r));
		Y[i].x->set(q, y);
		return y;
	}
	void set(int p, int q, ll x) { set(p, q, x, 0, N, root); }
} *T;
 
void init(int R, int C) {
	T=new seg2(R, C);
}
void update(int P, int Q, ll K) {
	T->set(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
	return T->get(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 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 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 505 ms 7028 KB Output is correct
5 Correct 378 ms 7364 KB Output is correct
6 Correct 430 ms 3916 KB Output is correct
7 Correct 470 ms 3860 KB Output is correct
8 Correct 331 ms 3204 KB Output is correct
9 Correct 449 ms 3780 KB Output is correct
10 Correct 414 ms 3512 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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 204 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 204 KB Output is correct
8 Correct 1 ms 204 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 332 KB Output is correct
12 Correct 872 ms 8848 KB Output is correct
13 Correct 1479 ms 4032 KB Output is correct
14 Correct 315 ms 1212 KB Output is correct
15 Correct 1741 ms 5304 KB Output is correct
16 Correct 203 ms 6596 KB Output is correct
17 Correct 711 ms 4648 KB Output is correct
18 Correct 1118 ms 6900 KB Output is correct
19 Correct 951 ms 7032 KB Output is correct
20 Correct 890 ms 6356 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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 204 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 204 KB Output is correct
8 Correct 1 ms 204 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 332 KB Output is correct
12 Correct 506 ms 6852 KB Output is correct
13 Correct 376 ms 7236 KB Output is correct
14 Correct 417 ms 3968 KB Output is correct
15 Correct 467 ms 3652 KB Output is correct
16 Correct 333 ms 3216 KB Output is correct
17 Correct 451 ms 3876 KB Output is correct
18 Correct 399 ms 3516 KB Output is correct
19 Correct 874 ms 8900 KB Output is correct
20 Correct 1472 ms 3944 KB Output is correct
21 Correct 320 ms 1052 KB Output is correct
22 Correct 1740 ms 5324 KB Output is correct
23 Correct 205 ms 6596 KB Output is correct
24 Correct 716 ms 4580 KB Output is correct
25 Correct 1110 ms 6896 KB Output is correct
26 Correct 950 ms 7052 KB Output is correct
27 Correct 888 ms 6468 KB Output is correct
28 Correct 583 ms 35396 KB Output is correct
29 Correct 1342 ms 34500 KB Output is correct
30 Correct 4042 ms 28976 KB Output is correct
31 Correct 3847 ms 48764 KB Output is correct
32 Correct 668 ms 10424 KB Output is correct
33 Correct 860 ms 12264 KB Output is correct
34 Correct 260 ms 27968 KB Output is correct
35 Correct 871 ms 21452 KB Output is correct
36 Correct 1588 ms 32112 KB Output is correct
37 Correct 1301 ms 32356 KB Output is correct
38 Correct 1307 ms 31956 KB Output is correct
39 Correct 1137 ms 27256 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 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 204 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 204 KB Output is correct
8 Correct 1 ms 204 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 332 KB Output is correct
12 Correct 509 ms 6852 KB Output is correct
13 Correct 393 ms 7276 KB Output is correct
14 Correct 420 ms 3928 KB Output is correct
15 Correct 459 ms 3608 KB Output is correct
16 Correct 329 ms 3320 KB Output is correct
17 Correct 439 ms 3784 KB Output is correct
18 Correct 418 ms 3440 KB Output is correct
19 Correct 882 ms 8884 KB Output is correct
20 Correct 1480 ms 4036 KB Output is correct
21 Correct 311 ms 1092 KB Output is correct
22 Correct 1728 ms 5224 KB Output is correct
23 Correct 201 ms 6564 KB Output is correct
24 Correct 704 ms 4492 KB Output is correct
25 Correct 1083 ms 6984 KB Output is correct
26 Correct 957 ms 6976 KB Output is correct
27 Correct 888 ms 6448 KB Output is correct
28 Correct 584 ms 35336 KB Output is correct
29 Correct 1329 ms 34324 KB Output is correct
30 Correct 4040 ms 28888 KB Output is correct
31 Correct 3880 ms 48708 KB Output is correct
32 Correct 647 ms 10480 KB Output is correct
33 Correct 853 ms 12288 KB Output is correct
34 Correct 266 ms 28152 KB Output is correct
35 Correct 879 ms 21408 KB Output is correct
36 Correct 1675 ms 32144 KB Output is correct
37 Correct 1330 ms 32440 KB Output is correct
38 Correct 1305 ms 31668 KB Output is correct
39 Correct 771 ms 64832 KB Output is correct
40 Correct 2072 ms 57648 KB Output is correct
41 Correct 5091 ms 53920 KB Output is correct
42 Correct 4982 ms 92928 KB Output is correct
43 Correct 461 ms 52424 KB Output is correct
44 Correct 928 ms 10764 KB Output is correct
45 Correct 1163 ms 27204 KB Output is correct
46 Correct 2259 ms 56524 KB Output is correct
47 Correct 2308 ms 56484 KB Output is correct
48 Correct 2155 ms 56004 KB Output is correct
49 Correct 1 ms 204 KB Output is correct