oj.uz

Submission #96970

# Submission time Handle Problem Language Result Execution time Memory
96970 2019-02-13T03:07:55 Z kig9981 Game (IOI13_game) C++17
63 / 100
 4387 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[100000], tree2[14444444];
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 164 ms 228088 KB Output is correct
2 Correct 169 ms 228128 KB Output is correct
3 Correct 192 ms 228060 KB Output is correct
4 Correct 194 ms 228304 KB Output is correct
5 Correct 182 ms 228088 KB Output is correct
6 Correct 161 ms 228084 KB Output is correct
7 Correct 188 ms 228052 KB Output is correct
8 Correct 156 ms 227960 KB Output is correct
9 Correct 165 ms 228060 KB Output is correct
10 Correct 158 ms 228088 KB Output is correct
11 Correct 170 ms 228088 KB Output is correct
12 Correct 155 ms 228088 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 227980 KB Output is correct
2 Correct 182 ms 228100 KB Output is correct
3 Correct 197 ms 228060 KB Output is correct
4 Correct 1672 ms 232280 KB Output is correct
5 Correct 1296 ms 232388 KB Output is correct
6 Correct 1879 ms 229240 KB Output is correct
7 Correct 1720 ms 229104 KB Output is correct
8 Correct 1107 ms 229860 KB Output is correct
9 Correct 1635 ms 228980 KB Output is correct
10 Correct 1712 ms 228668 KB Output is correct
11 Correct 171 ms 227980 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 228092 KB Output is correct
2 Correct 187 ms 228044 KB Output is correct
3 Correct 179 ms 228108 KB Output is correct
4 Correct 157 ms 228060 KB Output is correct
5 Correct 171 ms 228084 KB Output is correct
6 Correct 174 ms 228040 KB Output is correct
7 Correct 197 ms 227988 KB Output is correct
8 Correct 158 ms 228024 KB Output is correct
9 Correct 181 ms 228064 KB Output is correct
10 Correct 184 ms 228088 KB Output is correct
11 Correct 197 ms 228088 KB Output is correct
12 Correct 2544 ms 232088 KB Output is correct
13 Correct 3274 ms 228940 KB Output is correct
14 Correct 1072 ms 228600 KB Output is correct
15 Correct 3476 ms 228860 KB Output is correct
16 Correct 1229 ms 228856 KB Output is correct
17 Correct 2275 ms 229496 KB Output is correct
18 Correct 3529 ms 229264 KB Output is correct
19 Correct 3564 ms 229256 KB Output is correct
20 Correct 3260 ms 228856 KB Output is correct
21 Correct 159 ms 227960 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 228092 KB Output is correct
2 Correct 188 ms 227996 KB Output is correct
3 Correct 170 ms 228124 KB Output is correct
4 Correct 151 ms 227960 KB Output is correct
5 Correct 194 ms 227960 KB Output is correct
6 Correct 191 ms 227960 KB Output is correct
7 Correct 160 ms 228088 KB Output is correct
8 Correct 156 ms 228060 KB Output is correct
9 Correct 165 ms 227932 KB Output is correct
10 Correct 155 ms 228188 KB Output is correct
11 Correct 192 ms 227960 KB Output is correct
12 Correct 1296 ms 232188 KB Output is correct
13 Correct 1115 ms 232376 KB Output is correct
14 Correct 1491 ms 229240 KB Output is correct
15 Correct 2000 ms 228984 KB Output is correct
16 Correct 1149 ms 229624 KB Output is correct
17 Correct 1874 ms 229068 KB Output is correct
18 Correct 1793 ms 228732 KB Output is correct
19 Correct 2534 ms 232260 KB Output is correct
20 Correct 2990 ms 228984 KB Output is correct
21 Correct 965 ms 228756 KB Output is correct
22 Correct 3288 ms 229112 KB Output is correct
23 Correct 1124 ms 228776 KB Output is correct
24 Correct 2652 ms 229496 KB Output is correct
25 Correct 4387 ms 229240 KB Output is correct
26 Correct 3155 ms 229440 KB Output is correct
27 Correct 3121 ms 228892 KB Output is correct
28 Runtime error 1008 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 228044 KB Output is correct
2 Correct 187 ms 228088 KB Output is correct
3 Correct 172 ms 228088 KB Output is correct
4 Correct 173 ms 227932 KB Output is correct
5 Correct 166 ms 228036 KB Output is correct
6 Correct 190 ms 228076 KB Output is correct
7 Correct 148 ms 228060 KB Output is correct
8 Correct 155 ms 228040 KB Output is correct
9 Correct 152 ms 228060 KB Output is correct
10 Correct 156 ms 227960 KB Output is correct
11 Correct 164 ms 228196 KB Output is correct
12 Correct 1658 ms 232060 KB Output is correct
13 Correct 1130 ms 232468 KB Output is correct
14 Correct 1549 ms 229284 KB Output is correct
15 Correct 1734 ms 228924 KB Output is correct
16 Correct 1108 ms 229704 KB Output is correct
17 Correct 1890 ms 229016 KB Output is correct
18 Correct 1661 ms 228692 KB Output is correct
19 Correct 2359 ms 232192 KB Output is correct
20 Correct 3131 ms 228948 KB Output is correct
21 Correct 982 ms 228644 KB Output is correct
22 Correct 3759 ms 228936 KB Output is correct
23 Correct 1109 ms 228824 KB Output is correct
24 Correct 2438 ms 229420 KB Output is correct
25 Correct 3750 ms 229032 KB Output is correct
26 Correct 3828 ms 229348 KB Output is correct
27 Correct 3065 ms 228828 KB Output is correct
28 Runtime error 1006 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -