답안 #96970 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96970	2019-02-13T03:07:55 Z	kig9981	게임 (IOI13_game)	C++17	63 / 100	4387 ms	257024 KB

game

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #96970

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0