oj.uz

Submission #96966

# Submission time Handle Problem Language Result Execution time Memory
96966 2019-02-13T02:59:52 Z kig9981 Game (IOI13_game) C++17
63 / 100
 4006 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;
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(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=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 384 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1515 ms 35988 KB Output is correct
5 Correct 1215 ms 36028 KB Output is correct
6 Correct 1767 ms 34280 KB Output is correct
7 Correct 1581 ms 33452 KB Output is correct
8 Correct 948 ms 18028 KB Output is correct
9 Correct 1718 ms 33724 KB Output is correct
10 Correct 1740 ms 33352 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 2211 ms 11680 KB Output is correct
13 Correct 2890 ms 5440 KB Output is correct
14 Correct 824 ms 1372 KB Output is correct
15 Correct 3411 ms 8668 KB Output is correct
16 Correct 1018 ms 16976 KB Output is correct
17 Correct 2515 ms 9308 KB Output is correct
18 Correct 3806 ms 17404 KB Output is correct
19 Correct 3590 ms 17816 KB Output is correct
20 Correct 2841 ms 17256 KB Output is correct
21 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 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 512 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 1372 ms 36128 KB Output is correct
13 Correct 1105 ms 36144 KB Output is correct
14 Correct 1541 ms 34096 KB Output is correct
15 Correct 1614 ms 33340 KB Output is correct
16 Correct 1070 ms 17876 KB Output is correct
17 Correct 1713 ms 33724 KB Output is correct
18 Correct 1428 ms 33340 KB Output is correct
19 Correct 2089 ms 11628 KB Output is correct
20 Correct 3056 ms 5340 KB Output is correct
21 Correct 776 ms 1268 KB Output is correct
22 Correct 3484 ms 8668 KB Output is correct
23 Correct 1008 ms 16912 KB Output is correct
24 Correct 2448 ms 9436 KB Output is correct
25 Correct 4006 ms 17332 KB Output is correct
26 Correct 3838 ms 17876 KB Output is correct
27 Correct 3608 ms 17400 KB Output is correct
28 Correct 1382 ms 141472 KB Output is correct
29 Runtime error 3184 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1409 ms 35980 KB Output is correct
13 Correct 1229 ms 36144 KB Output is correct
14 Correct 1716 ms 34184 KB Output is correct
15 Correct 1729 ms 33468 KB Output is correct
16 Correct 1083 ms 18028 KB Output is correct
17 Correct 1832 ms 33724 KB Output is correct
18 Correct 1753 ms 33380 KB Output is correct
19 Correct 2235 ms 11856 KB Output is correct
20 Correct 2996 ms 5232 KB Output is correct
21 Correct 898 ms 1276 KB Output is correct
22 Correct 3447 ms 8668 KB Output is correct
23 Correct 894 ms 16848 KB Output is correct
24 Correct 2442 ms 9440 KB Output is correct
25 Correct 3991 ms 17392 KB Output is correct
26 Correct 3593 ms 17876 KB Output is correct
27 Correct 3468 ms 17440 KB Output is correct
28 Correct 1528 ms 141592 KB Output is correct
29 Runtime error 3702 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -