oj.uz

Submission #96977

# Submission time Handle Problem Language Result Execution time Memory
96977 2019-02-13T04:32:38 Z kig9981 Game (IOI13_game) C++17
80 / 100
 8061 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
struct Seg
{
	int l, r, p;
	long long v;
	Seg() : l(0), r(0), p(-1), v(0) {}
};
 
const int MAX=1e9;
Seg tree[222222], tree2[7777777];
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(tree2[p].p!=-1) return n1<=tree2[p].p && tree2[p].p<=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].p!=-1) {
		if(tree2[p].p==n) {
			tree2[p].v=v;
			return;
		}
		if(tree2[p].p<=m) {
			tree2[tree2[p].l=++tp2].p=tree2[p].p;
			tree2[tree2[p].l].v=tree2[p].v;
        }
        else {
            tree2[tree2[p].r=++tp2].p=tree2[p].p;
            tree2[tree2[p].r].v=tree2[p].v;
        }
        tree2[p].p=-1;
    }
    if(tree2[p].p==-1 && tree2[p].l==0 && tree2[p].r==0) {
        tree2[p].v=v;
        tree2[p].p=n;
        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 148 ms 188152 KB Output is correct
2 Correct 156 ms 188152 KB Output is correct
3 Correct 155 ms 188136 KB Output is correct
4 Correct 135 ms 188288 KB Output is correct
5 Correct 151 ms 188220 KB Output is correct
6 Correct 150 ms 188244 KB Output is correct
7 Correct 157 ms 188292 KB Output is correct
8 Correct 181 ms 188152 KB Output is correct
9 Correct 132 ms 188152 KB Output is correct
10 Correct 155 ms 188152 KB Output is correct
11 Correct 156 ms 188152 KB Output is correct
12 Correct 151 ms 188196 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 188212 KB Output is correct
2 Correct 151 ms 188312 KB Output is correct
3 Correct 150 ms 188220 KB Output is correct
4 Correct 1373 ms 192216 KB Output is correct
5 Correct 1162 ms 192708 KB Output is correct
6 Correct 1279 ms 189396 KB Output is correct
7 Correct 1544 ms 189164 KB Output is correct
8 Correct 1024 ms 189932 KB Output is correct
9 Correct 1650 ms 189228 KB Output is correct
10 Correct 1518 ms 188792 KB Output is correct
11 Correct 165 ms 188152 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 188212 KB Output is correct
2 Correct 156 ms 188136 KB Output is correct
3 Correct 189 ms 188124 KB Output is correct
4 Correct 153 ms 188152 KB Output is correct
5 Correct 146 ms 188300 KB Output is correct
6 Correct 151 ms 188152 KB Output is correct
7 Correct 162 ms 188160 KB Output is correct
8 Correct 157 ms 188152 KB Output is correct
9 Correct 144 ms 188152 KB Output is correct
10 Correct 128 ms 188152 KB Output is correct
11 Correct 134 ms 188152 KB Output is correct
12 Correct 2311 ms 192476 KB Output is correct
13 Correct 3426 ms 189104 KB Output is correct
14 Correct 1025 ms 188920 KB Output is correct
15 Correct 3654 ms 189116 KB Output is correct
16 Correct 1115 ms 188992 KB Output is correct
17 Correct 2311 ms 189620 KB Output is correct
18 Correct 4205 ms 189348 KB Output is correct
19 Correct 3487 ms 189664 KB Output is correct
20 Correct 3201 ms 189100 KB Output is correct
21 Correct 133 ms 188124 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 188184 KB Output is correct
2 Correct 156 ms 188152 KB Output is correct
3 Correct 148 ms 188156 KB Output is correct
4 Correct 135 ms 188152 KB Output is correct
5 Correct 154 ms 188152 KB Output is correct
6 Correct 157 ms 188208 KB Output is correct
7 Correct 144 ms 188204 KB Output is correct
8 Correct 130 ms 188200 KB Output is correct
9 Correct 151 ms 188152 KB Output is correct
10 Correct 134 ms 188248 KB Output is correct
11 Correct 140 ms 188152 KB Output is correct
12 Correct 1354 ms 192376 KB Output is correct
13 Correct 1175 ms 192660 KB Output is correct
14 Correct 1693 ms 189432 KB Output is correct
15 Correct 1705 ms 189176 KB Output is correct
16 Correct 970 ms 189844 KB Output is correct
17 Correct 1679 ms 189388 KB Output is correct
18 Correct 1621 ms 188920 KB Output is correct
19 Correct 2096 ms 192356 KB Output is correct
20 Correct 3299 ms 189216 KB Output is correct
21 Correct 993 ms 188868 KB Output is correct
22 Correct 3871 ms 188888 KB Output is correct
23 Correct 1026 ms 189120 KB Output is correct
24 Correct 2370 ms 189660 KB Output is correct
25 Correct 4094 ms 189412 KB Output is correct
26 Correct 3378 ms 189528 KB Output is correct
27 Correct 3210 ms 189044 KB Output is correct
28 Correct 980 ms 188804 KB Output is correct
29 Correct 2278 ms 194884 KB Output is correct
30 Correct 8061 ms 195824 KB Output is correct
31 Correct 7076 ms 196156 KB Output is correct
32 Correct 1085 ms 198044 KB Output is correct
33 Correct 1418 ms 198008 KB Output is correct
34 Correct 1569 ms 195868 KB Output is correct
35 Correct 1565 ms 199460 KB Output is correct
36 Correct 3411 ms 200080 KB Output is correct
37 Correct 2443 ms 200128 KB Output is correct
38 Correct 2444 ms 199620 KB Output is correct
39 Correct 2019 ms 199724 KB Output is correct
40 Correct 134 ms 188176 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 188176 KB Output is correct
2 Correct 142 ms 188280 KB Output is correct
3 Correct 133 ms 188124 KB Output is correct
4 Correct 157 ms 188284 KB Output is correct
5 Correct 144 ms 188312 KB Output is correct
6 Correct 147 ms 188216 KB Output is correct
7 Correct 140 ms 188104 KB Output is correct
8 Correct 139 ms 188200 KB Output is correct
9 Correct 150 ms 188152 KB Output is correct
10 Correct 135 ms 188212 KB Output is correct
11 Correct 153 ms 188152 KB Output is correct
12 Correct 1491 ms 192264 KB Output is correct
13 Correct 1087 ms 192648 KB Output is correct
14 Correct 1488 ms 189264 KB Output is correct
15 Correct 1575 ms 189136 KB Output is correct
16 Correct 1024 ms 189944 KB Output is correct
17 Correct 1435 ms 189152 KB Output is correct
18 Correct 1434 ms 188924 KB Output is correct
19 Correct 2286 ms 192500 KB Output is correct
20 Correct 3239 ms 189068 KB Output is correct
21 Correct 955 ms 188924 KB Output is correct
22 Correct 3696 ms 188988 KB Output is correct
23 Correct 1092 ms 189116 KB Output is correct
24 Correct 2053 ms 189680 KB Output is correct
25 Correct 3540 ms 189368 KB Output is correct
26 Correct 3123 ms 189624 KB Output is correct
27 Correct 2876 ms 188948 KB Output is correct
28 Correct 793 ms 188832 KB Output is correct
29 Correct 2041 ms 195004 KB Output is correct
30 Correct 7374 ms 195692 KB Output is correct
31 Correct 6942 ms 196040 KB Output is correct
32 Correct 1128 ms 198056 KB Output is correct
33 Correct 1388 ms 198036 KB Output is correct
34 Correct 1366 ms 195916 KB Output is correct
35 Correct 1460 ms 199460 KB Output is correct
36 Correct 2978 ms 199884 KB Output is correct
37 Correct 2210 ms 200188 KB Output is correct
38 Correct 2351 ms 199688 KB Output is correct
39 Runtime error 970 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -