oj.uz

Submission #96972

# Submission time Handle Problem Language Result Execution time Memory
96972 2019-02-13T03:11:12 Z kig9981 Game (IOI13_game) C++17
63 / 100
 4348 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
struct Seg
{
	int l, r;
	long long v;
	Seg() : l(0), r(0), v(0) {}
};
 
const int MAX=1e9;
Seg tree[222222], tree2[15555555];
int tp1=1, tp2;
 
long long GCD(long long a, long long b)
{
	for(;b;a%=b,swap(a,b));
	return a;
}
 
long long get_gcd2(int n1, int n2, int p, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(p==0 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tree2[p].v;
	return GCD(get_gcd2(n1,n2,tree2[p].l,s,m),get_gcd2(n1,n2,tree2[p].r,m+1,e));
}
 
long long get_gcd(int x1, int x2, int y1, int y2, int p=1, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(p==0 || x2<s || e<x1) return 0;
	if(x1<=s && e<=x2) return get_gcd2(y1,y2,tree[p].v);
	return GCD(get_gcd(x1,x2,y1,y2,tree[p].l,s,m),get_gcd(x1,x2,y1,y2,tree[p].r,m+1,e));
}
 
void set_tree2(int n, long long v, int p, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree2[p].v=v;
		return;
	}
	if(n<=m) {
		if(tree2[p].l==0) tree2[p].l=++tp2;
		set_tree2(n,v,tree2[p].l,s,m);
	}
	else {
		if(tree2[p].r==0) tree2[p].r=++tp2;
		set_tree2(n,v,tree2[p].r,m+1,e);
	}
	tree2[p].v=GCD(tree2[tree2[p].l].v,tree2[tree2[p].r].v);
}
 
void set_tree(int x, int y, long long v, int p=1, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(tree[p].v==0) tree[p].v=++tp2;
	if(s==e) {
        set_tree2(y,v,tree[p].v);
        return;
    }
	if(x<=m) {
		if(tree[p].l==0) tree[p].l=++tp1;
		set_tree(x,y,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=++tp1;
		set_tree(x,y,v,tree[p].r,m+1,e);
	}
    set_tree2(y,GCD(get_gcd2(y,y,tree[tree[p].l].v),get_gcd2(y,y,tree[tree[p].r].v)),tree[p].v);
}
 
void init(int R, int C) {}
 
void update(int P, int Q, long long K) {set_tree(P,Q,K);}
 
long long calculate(int P, int Q, int U, int V) {return get_gcd(P,U,Q,V);}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 247544 KB Output is correct
2 Correct 217 ms 247288 KB Output is correct
3 Correct 217 ms 247416 KB Output is correct
4 Correct 188 ms 247416 KB Output is correct
5 Correct 186 ms 247316 KB Output is correct
6 Correct 188 ms 247288 KB Output is correct
7 Correct 186 ms 247384 KB Output is correct
8 Correct 208 ms 247416 KB Output is correct
9 Correct 189 ms 247420 KB Output is correct
10 Correct 207 ms 247288 KB Output is correct
11 Correct 205 ms 247416 KB Output is correct
12 Correct 203 ms 247420 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 247364 KB Output is correct
2 Correct 176 ms 247416 KB Output is correct
3 Correct 191 ms 247384 KB Output is correct
4 Correct 1545 ms 251512 KB Output is correct
5 Correct 1187 ms 251644 KB Output is correct
6 Correct 1592 ms 248428 KB Output is correct
7 Correct 1655 ms 248440 KB Output is correct
8 Correct 1103 ms 248964 KB Output is correct
9 Correct 1585 ms 248324 KB Output is correct
10 Correct 1535 ms 248016 KB Output is correct
11 Correct 202 ms 247288 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 247336 KB Output is correct
2 Correct 216 ms 247348 KB Output is correct
3 Correct 203 ms 247288 KB Output is correct
4 Correct 173 ms 247416 KB Output is correct
5 Correct 178 ms 247288 KB Output is correct
6 Correct 191 ms 247416 KB Output is correct
7 Correct 186 ms 247288 KB Output is correct
8 Correct 202 ms 247416 KB Output is correct
9 Correct 205 ms 247300 KB Output is correct
10 Correct 209 ms 247288 KB Output is correct
11 Correct 199 ms 247288 KB Output is correct
12 Correct 2327 ms 251600 KB Output is correct
13 Correct 3188 ms 248232 KB Output is correct
14 Correct 1018 ms 248004 KB Output is correct
15 Correct 3781 ms 248212 KB Output is correct
16 Correct 1115 ms 248184 KB Output is correct
17 Correct 2244 ms 248732 KB Output is correct
18 Correct 3551 ms 248568 KB Output is correct
19 Correct 3201 ms 248756 KB Output is correct
20 Correct 3102 ms 248220 KB Output is correct
21 Correct 176 ms 247368 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 247380 KB Output is correct
2 Correct 191 ms 247288 KB Output is correct
3 Correct 177 ms 247288 KB Output is correct
4 Correct 186 ms 247288 KB Output is correct
5 Correct 192 ms 247388 KB Output is correct
6 Correct 190 ms 247432 KB Output is correct
7 Correct 180 ms 247288 KB Output is correct
8 Correct 205 ms 247420 KB Output is correct
9 Correct 195 ms 247416 KB Output is correct
10 Correct 171 ms 247288 KB Output is correct
11 Correct 198 ms 247396 KB Output is correct
12 Correct 1369 ms 251640 KB Output is correct
13 Correct 1180 ms 251768 KB Output is correct
14 Correct 1613 ms 248544 KB Output is correct
15 Correct 1790 ms 248340 KB Output is correct
16 Correct 1244 ms 249208 KB Output is correct
17 Correct 1674 ms 248336 KB Output is correct
18 Correct 1664 ms 248064 KB Output is correct
19 Correct 2033 ms 251472 KB Output is correct
20 Correct 3088 ms 248312 KB Output is correct
21 Correct 1037 ms 248056 KB Output is correct
22 Correct 3799 ms 248212 KB Output is correct
23 Correct 1169 ms 248136 KB Output is correct
24 Correct 2671 ms 248948 KB Output is correct
25 Correct 3646 ms 248668 KB Output is correct
26 Correct 3380 ms 248768 KB Output is correct
27 Correct 3142 ms 248160 KB Output is correct
28 Correct 1215 ms 247940 KB Output is correct
29 Runtime error 2949 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 247260 KB Output is correct
2 Correct 183 ms 247288 KB Output is correct
3 Correct 204 ms 247340 KB Output is correct
4 Correct 198 ms 247416 KB Output is correct
5 Correct 189 ms 247356 KB Output is correct
6 Correct 198 ms 247288 KB Output is correct
7 Correct 171 ms 247292 KB Output is correct
8 Correct 205 ms 247336 KB Output is correct
9 Correct 210 ms 247288 KB Output is correct
10 Correct 205 ms 247416 KB Output is correct
11 Correct 195 ms 247388 KB Output is correct
12 Correct 1415 ms 251532 KB Output is correct
13 Correct 1200 ms 251768 KB Output is correct
14 Correct 1704 ms 248548 KB Output is correct
15 Correct 1929 ms 248192 KB Output is correct
16 Correct 1214 ms 249084 KB Output is correct
17 Correct 1931 ms 248420 KB Output is correct
18 Correct 1651 ms 247932 KB Output is correct
19 Correct 2410 ms 251524 KB Output is correct
20 Correct 3131 ms 248312 KB Output is correct
21 Correct 1047 ms 247996 KB Output is correct
22 Correct 3738 ms 248348 KB Output is correct
23 Correct 1159 ms 248108 KB Output is correct
24 Correct 2501 ms 248692 KB Output is correct
25 Correct 4348 ms 248556 KB Output is correct
26 Correct 4030 ms 248720 KB Output is correct
27 Correct 3659 ms 248020 KB Output is correct
28 Correct 1286 ms 248056 KB Output is correct
29 Runtime error 3404 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
30 Halted 0 ms 0 KB -