답안 #96966 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96966	2019-02-13T02:59:52 Z	kig9981	게임 (IOI13_game)	C++17	63 / 100	4006 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;
vector<Seg> tree(2), tree2(1);
 
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=tree2.size(), tree2.push_back(Seg());
		set_tree2(n,v,tree2[p].l,s,m);
	}
	else {
		if(tree2[p].r==0) tree2[p].r=tree2.size(), tree2.push_back(Seg());
		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=tree2.size(), tree2.push_back(Seg());
	
	if(s==e) {
        set_tree2(y,v,tree[p].v);
        return;
    }
	if(x<=m) {
		if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
		set_tree(x,y,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
		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	3 ms	384 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	7 ms	768 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	4 ms	640 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1515 ms	35988 KB	Output is correct
5	Correct	1215 ms	36028 KB	Output is correct
6	Correct	1767 ms	34280 KB	Output is correct
7	Correct	1581 ms	33452 KB	Output is correct
8	Correct	948 ms	18028 KB	Output is correct
9	Correct	1718 ms	33724 KB	Output is correct
10	Correct	1740 ms	33352 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	7 ms	640 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	4 ms	640 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	2211 ms	11680 KB	Output is correct
13	Correct	2890 ms	5440 KB	Output is correct
14	Correct	824 ms	1372 KB	Output is correct
15	Correct	3411 ms	8668 KB	Output is correct
16	Correct	1018 ms	16976 KB	Output is correct
17	Correct	2515 ms	9308 KB	Output is correct
18	Correct	3806 ms	17404 KB	Output is correct
19	Correct	3590 ms	17816 KB	Output is correct
20	Correct	2841 ms	17256 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	8 ms	640 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	512 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	1372 ms	36128 KB	Output is correct
13	Correct	1105 ms	36144 KB	Output is correct
14	Correct	1541 ms	34096 KB	Output is correct
15	Correct	1614 ms	33340 KB	Output is correct
16	Correct	1070 ms	17876 KB	Output is correct
17	Correct	1713 ms	33724 KB	Output is correct
18	Correct	1428 ms	33340 KB	Output is correct
19	Correct	2089 ms	11628 KB	Output is correct
20	Correct	3056 ms	5340 KB	Output is correct
21	Correct	776 ms	1268 KB	Output is correct
22	Correct	3484 ms	8668 KB	Output is correct
23	Correct	1008 ms	16912 KB	Output is correct
24	Correct	2448 ms	9436 KB	Output is correct
25	Correct	4006 ms	17332 KB	Output is correct
26	Correct	3838 ms	17876 KB	Output is correct
27	Correct	3608 ms	17400 KB	Output is correct
28	Correct	1382 ms	141472 KB	Output is correct
29	Runtime error	3184 ms	257024 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	6 ms	768 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	7 ms	640 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	4 ms	640 KB	Output is correct
11	Correct	5 ms	512 KB	Output is correct
12	Correct	1409 ms	35980 KB	Output is correct
13	Correct	1229 ms	36144 KB	Output is correct
14	Correct	1716 ms	34184 KB	Output is correct
15	Correct	1729 ms	33468 KB	Output is correct
16	Correct	1083 ms	18028 KB	Output is correct
17	Correct	1832 ms	33724 KB	Output is correct
18	Correct	1753 ms	33380 KB	Output is correct
19	Correct	2235 ms	11856 KB	Output is correct
20	Correct	2996 ms	5232 KB	Output is correct
21	Correct	898 ms	1276 KB	Output is correct
22	Correct	3447 ms	8668 KB	Output is correct
23	Correct	894 ms	16848 KB	Output is correct
24	Correct	2442 ms	9440 KB	Output is correct
25	Correct	3991 ms	17392 KB	Output is correct
26	Correct	3593 ms	17876 KB	Output is correct
27	Correct	3468 ms	17440 KB	Output is correct
28	Correct	1528 ms	141592 KB	Output is correct
29	Runtime error	3702 ms	257024 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Halted	0 ms	0 KB	-

답안 #96966

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