oj.uz

Submission #96968

# Submission time Handle Problem Language Result Execution time Memory
96968 2019-02-13T03:04:13 Z kig9981 Game (IOI13_game) C++17
63 / 100
 4123 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[11111111];
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 120 ms 175864 KB Output is correct
2 Correct 143 ms 175900 KB Output is correct
3 Correct 123 ms 175864 KB Output is correct
4 Correct 122 ms 175804 KB Output is correct
5 Correct 142 ms 175920 KB Output is correct
6 Correct 143 ms 175864 KB Output is correct
7 Correct 138 ms 175864 KB Output is correct
8 Correct 121 ms 175864 KB Output is correct
9 Correct 124 ms 175864 KB Output is correct
10 Correct 125 ms 175876 KB Output is correct
11 Correct 119 ms 175864 KB Output is correct
12 Correct 159 ms 175784 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 175880 KB Output is correct
2 Correct 140 ms 175864 KB Output is correct
3 Correct 140 ms 175924 KB Output is correct
4 Correct 1538 ms 179956 KB Output is correct
5 Correct 1332 ms 180316 KB Output is correct
6 Correct 1514 ms 177116 KB Output is correct
7 Correct 1618 ms 176760 KB Output is correct
8 Correct 1038 ms 177528 KB Output is correct
9 Correct 1766 ms 176768 KB Output is correct
10 Correct 1584 ms 176524 KB Output is correct
11 Correct 118 ms 175864 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 175808 KB Output is correct
2 Correct 124 ms 175864 KB Output is correct
3 Correct 132 ms 175844 KB Output is correct
4 Correct 144 ms 175864 KB Output is correct
5 Correct 148 ms 175860 KB Output is correct
6 Correct 148 ms 175864 KB Output is correct
7 Correct 144 ms 175864 KB Output is correct
8 Correct 123 ms 175868 KB Output is correct
9 Correct 144 ms 175864 KB Output is correct
10 Correct 151 ms 175836 KB Output is correct
11 Correct 142 ms 175864 KB Output is correct
12 Correct 2153 ms 180044 KB Output is correct
13 Correct 3262 ms 176744 KB Output is correct
14 Correct 1022 ms 176376 KB Output is correct
15 Correct 3731 ms 176792 KB Output is correct
16 Correct 1008 ms 176692 KB Output is correct
17 Correct 2325 ms 177324 KB Output is correct
18 Correct 4086 ms 176976 KB Output is correct
19 Correct 3687 ms 177140 KB Output is correct
20 Correct 3557 ms 176764 KB Output is correct
21 Correct 135 ms 175936 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 175792 KB Output is correct
2 Correct 141 ms 176052 KB Output is correct
3 Correct 119 ms 175864 KB Output is correct
4 Correct 128 ms 175856 KB Output is correct
5 Correct 129 ms 175864 KB Output is correct
6 Correct 140 ms 175756 KB Output is correct
7 Correct 132 ms 175932 KB Output is correct
8 Correct 152 ms 175864 KB Output is correct
9 Correct 134 ms 175864 KB Output is correct
10 Correct 129 ms 175888 KB Output is correct
11 Correct 128 ms 175868 KB Output is correct
12 Correct 1398 ms 179860 KB Output is correct
13 Correct 1270 ms 180320 KB Output is correct
14 Correct 1704 ms 176968 KB Output is correct
15 Correct 1628 ms 176888 KB Output is correct
16 Correct 1204 ms 177628 KB Output is correct
17 Correct 1852 ms 176712 KB Output is correct
18 Correct 1506 ms 176600 KB Output is correct
19 Correct 2295 ms 179960 KB Output is correct
20 Correct 2939 ms 176632 KB Output is correct
21 Correct 1018 ms 176552 KB Output is correct
22 Correct 3582 ms 176856 KB Output is correct
23 Correct 1103 ms 176720 KB Output is correct
24 Correct 2266 ms 177352 KB Output is correct
25 Correct 4123 ms 177048 KB Output is correct
26 Correct 3656 ms 177204 KB Output is correct
27 Correct 3309 ms 176552 KB Output is correct
28 Runtime error 853 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 147 ms 175832 KB Output is correct
2 Correct 162 ms 175812 KB Output is correct
3 Correct 144 ms 175836 KB Output is correct
4 Correct 145 ms 175940 KB Output is correct
5 Correct 160 ms 175864 KB Output is correct
6 Correct 135 ms 175964 KB Output is correct
7 Correct 135 ms 175948 KB Output is correct
8 Correct 151 ms 175796 KB Output is correct
9 Correct 132 ms 175876 KB Output is correct
10 Correct 143 ms 175844 KB Output is correct
11 Correct 133 ms 175864 KB Output is correct
12 Correct 1483 ms 179896 KB Output is correct
13 Correct 1051 ms 180216 KB Output is correct
14 Correct 1779 ms 177036 KB Output is correct
15 Correct 1630 ms 176760 KB Output is correct
16 Correct 915 ms 177528 KB Output is correct
17 Correct 1742 ms 176788 KB Output is correct
18 Correct 1499 ms 176376 KB Output is correct
19 Correct 2289 ms 179960 KB Output is correct
20 Correct 3329 ms 176740 KB Output is correct
21 Correct 949 ms 176504 KB Output is correct
22 Correct 3391 ms 176632 KB Output is correct
23 Correct 1204 ms 176700 KB Output is correct
24 Correct 2574 ms 177288 KB Output is correct
25 Correct 3838 ms 177044 KB Output is correct
26 Correct 3802 ms 177248 KB Output is correct
27 Correct 3535 ms 176552 KB Output is correct
28 Runtime error 904 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -