답안 #96968 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96968	2019-02-13T03:04:13 Z	kig9981	게임 (IOI13_game)	C++17	63 / 100	4123 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[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

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

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

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

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

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

답안 #96968

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