oj.uz

Submission #96981

# Submission time Handle Problem Language Result Execution time Memory
96981 2019-02-13T04:52:59 Z kig9981 Game (IOI13_game) C++17
100 / 100
 8939 ms 58592 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;
vector<Seg> tree(2), tree2(1);
 
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(tree2[p].l<0) return n1<=-tree2[p].l-1 && -tree2[p].l-1<=n2 ? tree2[p].v: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(tree2[p].l<0) {
        int t=-tree2[p].l-1;
		if(t==n) {
			tree2[p].v=v;
			return;
		}
        tree2[p].l=0;
		if(t<=m) {
            tree2[p].l=tree2.size(), tree2.push_back(Seg());
			tree2[tree2[p].l].l=-t-1;
			tree2[tree2[p].l].v=tree2[p].v;
        }
        else {
            tree2[p].r=tree2.size(), tree2.push_back(Seg());
            tree2[tree2[p].r].l=-t-1;
            tree2[tree2[p].r].v=tree2[p].v;
        }
    }
    if(tree2[p].l==0 && tree2[p].r==0) {
        tree2[p].v=v;
        tree2[p].l=-n-1;
        return;
    }
	if(n<=m) {
		if(tree2[p].l==0) tree2[p].l=tree2.size(), tree2.push_back(Seg());
		set_tree2(n,v,tree2[p].l,s,m);
	}
	else {
		if(tree2[p].r==0) tree2[p].r=tree2.size(), tree2.push_back(Seg());
		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=tree2.size(), tree2.push_back(Seg());
	if(s==e) {
        set_tree2(y,v,tree[p].v);
        return;
    }
	if(x<=m) {
		if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
		set_tree(x,y,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
		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 3 ms 256 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 1343 ms 20028 KB Output is correct
5 Correct 916 ms 20332 KB Output is correct
6 Correct 1341 ms 17772 KB Output is correct
7 Correct 1519 ms 16904 KB Output is correct
8 Correct 746 ms 9948 KB Output is correct
9 Correct 1437 ms 17384 KB Output is correct
10 Correct 1489 ms 17232 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 432 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 2245 ms 8592 KB Output is correct
13 Correct 3028 ms 4580 KB Output is correct
14 Correct 831 ms 1164 KB Output is correct
15 Correct 3597 ms 9468 KB Output is correct
16 Correct 971 ms 8668 KB Output is correct
17 Correct 2009 ms 5720 KB Output is correct
18 Correct 3786 ms 9004 KB Output is correct
19 Correct 3253 ms 9580 KB Output is correct
20 Correct 2408 ms 9308 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 392 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1198 ms 19992 KB Output is correct
13 Correct 906 ms 20308 KB Output is correct
14 Correct 1302 ms 17848 KB Output is correct
15 Correct 1252 ms 16976 KB Output is correct
16 Correct 742 ms 10112 KB Output is correct
17 Correct 1271 ms 17232 KB Output is correct
18 Correct 1275 ms 16940 KB Output is correct
19 Correct 1982 ms 8604 KB Output is correct
20 Correct 2868 ms 4580 KB Output is correct
21 Correct 839 ms 1284 KB Output is correct
22 Correct 3574 ms 9532 KB Output is correct
23 Correct 1138 ms 8740 KB Output is correct
24 Correct 1723 ms 5672 KB Output is correct
25 Correct 3382 ms 8984 KB Output is correct
26 Correct 2584 ms 9472 KB Output is correct
27 Correct 2503 ms 9080 KB Output is correct
28 Correct 900 ms 23552 KB Output is correct
29 Correct 1922 ms 18372 KB Output is correct
30 Correct 7138 ms 20020 KB Output is correct
31 Correct 7050 ms 12656 KB Output is correct
32 Correct 940 ms 1364 KB Output is correct
33 Correct 1313 ms 2568 KB Output is correct
34 Correct 1405 ms 15524 KB Output is correct
35 Correct 1653 ms 8480 KB Output is correct
36 Correct 2900 ms 15648 KB Output is correct
37 Correct 2168 ms 15836 KB Output is correct
38 Correct 2317 ms 15548 KB Output is correct
39 Correct 1659 ms 13452 KB Output is correct
40 Correct 3 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 1188 ms 20176 KB Output is correct
13 Correct 994 ms 20188 KB Output is correct
14 Correct 1228 ms 17776 KB Output is correct
15 Correct 1312 ms 17068 KB Output is correct
16 Correct 755 ms 10052 KB Output is correct
17 Correct 1378 ms 17232 KB Output is correct
18 Correct 1257 ms 16924 KB Output is correct
19 Correct 2168 ms 8628 KB Output is correct
20 Correct 2987 ms 4580 KB Output is correct
21 Correct 954 ms 1368 KB Output is correct
22 Correct 3693 ms 9360 KB Output is correct
23 Correct 947 ms 8796 KB Output is correct
24 Correct 1848 ms 5832 KB Output is correct
25 Correct 3924 ms 9052 KB Output is correct
26 Correct 3106 ms 9500 KB Output is correct
27 Correct 3129 ms 9204 KB Output is correct
28 Correct 910 ms 23776 KB Output is correct
29 Correct 2280 ms 18404 KB Output is correct
30 Correct 7380 ms 20064 KB Output is correct
31 Correct 7327 ms 12536 KB Output is correct
32 Correct 1072 ms 1268 KB Output is correct
33 Correct 1280 ms 2676 KB Output is correct
34 Correct 1295 ms 15564 KB Output is correct
35 Correct 1353 ms 8548 KB Output is correct
36 Correct 2778 ms 15940 KB Output is correct
37 Correct 2203 ms 16120 KB Output is correct
38 Correct 2203 ms 15440 KB Output is correct
39 Correct 972 ms 49572 KB Output is correct
40 Correct 3082 ms 58592 KB Output is correct
41 Correct 8939 ms 40504 KB Output is correct
42 Correct 8874 ms 43512 KB Output is correct
43 Correct 1863 ms 47160 KB Output is correct
44 Correct 1359 ms 10864 KB Output is correct
45 Correct 2093 ms 23804 KB Output is correct
46 Correct 4226 ms 56556 KB Output is correct
47 Correct 4347 ms 56712 KB Output is correct
48 Correct 4103 ms 56016 KB Output is correct
49 Correct 3 ms 384 KB Output is correct