답안 #64699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64699	2018-08-05T12:21:37 Z	TadijaSebez	게임 (IOI13_game)	C++11	80 / 100	10965 ms	257024 KB

game

#include "game.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <ctime>
using namespace std;
#define mp make_pair
#define ll long long
const int N=200050;
const int M=N*64*2;
ll gcd(ll x, ll y){ return __gcd(x,y);}
int ls[M],rs[M],root,tsz,rt[M],y[M],L[M],R[M];
pair<int,int> id[M];
ll val[M],my[M];
int MakeNode(pair<int,int> p, ll g)
{
	tsz++;
	y[tsz]=rand();
	my[tsz]=val[tsz]=g;
	L[tsz]=R[tsz]=p.first;
	id[tsz]=p;
	return tsz;
}
void Take(int c)
{
	if(!c) return;
	val[c]=my[c];
	L[c]=id[c].first;
	R[c]=id[c].first;
	if(ls[c]) val[c]=gcd(val[c],val[ls[c]]),L[c]=L[ls[c]];
	if(rs[c]) val[c]=gcd(val[c],val[rs[c]]),R[c]=R[rs[c]];
}
void Rotate1(int &c)
{
	int a=ls[c],b=rs[a];
	ls[c]=b;
	rs[a]=c;
	Take(c);Take(a);
	c=a;
}
void Rotate2(int &c)
{
	int a=rs[c],b=ls[a];
	rs[c]=b;
	ls[a]=c;
	Take(c);Take(a);
	c=a;
}
void Add(int &c, pair<int,int> p, ll g)
{
	if(!c){ c=MakeNode(p,g);return;}
	if(p==id[c])
	{
		my[c]=g;
		Take(c);
	}
	else if(p<id[c])
	{
		Add(ls[c],p,g);
		if(y[ls[c]]>y[c]) Rotate1(c);
		else Take(c);
	}
	else
	{
		Add(rs[c],p,g);
		if(y[rs[c]]>y[c]) Rotate2(c);
		else Take(c);
	}
}
ll Get(int c, int l, int r)
{
	if(!c || L[c]>r || R[c]<l) return 0;
	if(l<=L[c] && r>=R[c]) return val[c];
	ll ans=0;
	if(id[c].first>=l && id[c].first<=r) ans=my[c];
	ans=gcd(ans,Get(ls[c],l,r));
	ans=gcd(ans,Get(rs[c],l,r));
	return ans;
}
void Set(int &c, int ss, int se, int x, int y, ll g)
{
	if(!c) c=++tsz;
	Add(rt[c],mp(y,x),g);
	if(ss==se) return;
	int mid=ss+se>>1;
	if(x<=mid) Set(ls[c],ss,mid,x,y,g);
	else Set(rs[c],mid+1,se,x,y,g);
}
ll Get(int c, int ss, int se, int qs, int qe, int l, int r)
{
	if(!c || ss>qe || qs>se) return 0;
	if(qs<=ss && qe>=se) return Get(rt[c],l,r);
	int mid=ss+se>>1;
	return gcd(Get(ls[c],ss,mid,qs,qe,l,r),Get(rs[c],mid+1,se,qs,qe,l,r));
}
int n,m;
void init(int R, int C){ srand(time(0));n=R;m=C;}
void update(int x, int y, ll g){ Set(root,0,n-1,x,y,g);}
void Swap(int &a, int &b){ a^=b,b^=a,a^=b;}
ll calculate(int x1, int y1, int x2, int y2){ if(x1>x2) Swap(x1,x2);if(y1>y2) Swap(y1,y2);return Get(root,0,n-1,x1,x2,y1,y2);}

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;
      ^~~
game.cpp: In function 'void Set(int&, int, int, int, int, long long int)':
game.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
game.cpp: In function 'long long int Get(int, int, int, int, int, int, int)':
game.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	3 ms	612 KB	Output is correct
4	Correct	2 ms	612 KB	Output is correct
5	Correct	2 ms	612 KB	Output is correct
6	Correct	4 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	3 ms	628 KB	Output is correct
10	Correct	2 ms	628 KB	Output is correct
11	Correct	3 ms	628 KB	Output is correct
12	Correct	2 ms	628 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	636 KB	Output is correct
2	Correct	2 ms	644 KB	Output is correct
3	Correct	3 ms	668 KB	Output is correct
4	Correct	1293 ms	11136 KB	Output is correct
5	Correct	437 ms	15340 KB	Output is correct
6	Correct	1049 ms	16832 KB	Output is correct
7	Correct	1387 ms	21304 KB	Output is correct
8	Correct	671 ms	25272 KB	Output is correct
9	Correct	1122 ms	30136 KB	Output is correct
10	Correct	1261 ms	34168 KB	Output is correct
11	Correct	2 ms	34168 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	34168 KB	Output is correct
2	Correct	2 ms	34168 KB	Output is correct
3	Correct	5 ms	34168 KB	Output is correct
4	Correct	3 ms	34168 KB	Output is correct
5	Correct	3 ms	34168 KB	Output is correct
6	Correct	3 ms	34168 KB	Output is correct
7	Correct	4 ms	34168 KB	Output is correct
8	Correct	4 ms	34168 KB	Output is correct
9	Correct	3 ms	34168 KB	Output is correct
10	Correct	3 ms	34168 KB	Output is correct
11	Correct	3 ms	34168 KB	Output is correct
12	Correct	2041 ms	44388 KB	Output is correct
13	Correct	4837 ms	44388 KB	Output is correct
14	Correct	502 ms	44388 KB	Output is correct
15	Correct	4871 ms	44388 KB	Output is correct
16	Correct	553 ms	44388 KB	Output is correct
17	Correct	1742 ms	44388 KB	Output is correct
18	Correct	3729 ms	44388 KB	Output is correct
19	Correct	2915 ms	44388 KB	Output is correct
20	Correct	3146 ms	44724 KB	Output is correct
21	Correct	2 ms	44724 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	44724 KB	Output is correct
2	Correct	2 ms	44724 KB	Output is correct
3	Correct	3 ms	44724 KB	Output is correct
4	Correct	2 ms	44724 KB	Output is correct
5	Correct	2 ms	44724 KB	Output is correct
6	Correct	4 ms	44724 KB	Output is correct
7	Correct	3 ms	44724 KB	Output is correct
8	Correct	3 ms	44724 KB	Output is correct
9	Correct	3 ms	44724 KB	Output is correct
10	Correct	3 ms	44724 KB	Output is correct
11	Correct	3 ms	44724 KB	Output is correct
12	Correct	1227 ms	44724 KB	Output is correct
13	Correct	485 ms	45104 KB	Output is correct
14	Correct	1074 ms	45104 KB	Output is correct
15	Correct	1503 ms	45104 KB	Output is correct
16	Correct	793 ms	45104 KB	Output is correct
17	Correct	1240 ms	45104 KB	Output is correct
18	Correct	1202 ms	45104 KB	Output is correct
19	Correct	2093 ms	48012 KB	Output is correct
20	Correct	4554 ms	48012 KB	Output is correct
21	Correct	513 ms	48012 KB	Output is correct
22	Correct	4763 ms	48012 KB	Output is correct
23	Correct	452 ms	48012 KB	Output is correct
24	Correct	1734 ms	48012 KB	Output is correct
25	Correct	3543 ms	48012 KB	Output is correct
26	Correct	2627 ms	48012 KB	Output is correct
27	Correct	2887 ms	48012 KB	Output is correct
28	Correct	1111 ms	62468 KB	Output is correct
29	Correct	4208 ms	65476 KB	Output is correct
30	Correct	6594 ms	65476 KB	Output is correct
31	Correct	5618 ms	65476 KB	Output is correct
32	Correct	731 ms	65476 KB	Output is correct
33	Correct	1188 ms	65476 KB	Output is correct
34	Correct	549 ms	65476 KB	Output is correct
35	Correct	2529 ms	65476 KB	Output is correct
36	Correct	5323 ms	65476 KB	Output is correct
37	Correct	3719 ms	65476 KB	Output is correct
38	Correct	3797 ms	65476 KB	Output is correct
39	Correct	3170 ms	65476 KB	Output is correct
40	Correct	3 ms	65476 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	65476 KB	Output is correct
2	Correct	4 ms	65476 KB	Output is correct
3	Correct	3 ms	65476 KB	Output is correct
4	Correct	3 ms	65476 KB	Output is correct
5	Correct	3 ms	65476 KB	Output is correct
6	Correct	3 ms	65476 KB	Output is correct
7	Correct	3 ms	65476 KB	Output is correct
8	Correct	2 ms	65476 KB	Output is correct
9	Correct	3 ms	65476 KB	Output is correct
10	Correct	4 ms	65476 KB	Output is correct
11	Correct	3 ms	65476 KB	Output is correct
12	Correct	1323 ms	65476 KB	Output is correct
13	Correct	478 ms	65476 KB	Output is correct
14	Correct	1060 ms	65476 KB	Output is correct
15	Correct	1320 ms	65476 KB	Output is correct
16	Correct	837 ms	65476 KB	Output is correct
17	Correct	1384 ms	65476 KB	Output is correct
18	Correct	1358 ms	65476 KB	Output is correct
19	Correct	2105 ms	65476 KB	Output is correct
20	Correct	4341 ms	65476 KB	Output is correct
21	Correct	460 ms	65476 KB	Output is correct
22	Correct	4820 ms	65476 KB	Output is correct
23	Correct	443 ms	65476 KB	Output is correct
24	Correct	1866 ms	66380 KB	Output is correct
25	Correct	3397 ms	74168 KB	Output is correct
26	Correct	2746 ms	79592 KB	Output is correct
27	Correct	3310 ms	84432 KB	Output is correct
28	Correct	1031 ms	111840 KB	Output is correct
29	Correct	3525 ms	114468 KB	Output is correct
30	Correct	6328 ms	114720 KB	Output is correct
31	Correct	5462 ms	117012 KB	Output is correct
32	Correct	719 ms	117012 KB	Output is correct
33	Correct	1016 ms	121320 KB	Output is correct
34	Correct	562 ms	147728 KB	Output is correct
35	Correct	2053 ms	147728 KB	Output is correct
36	Correct	5031 ms	166184 KB	Output is correct
37	Correct	3384 ms	175520 KB	Output is correct
38	Correct	3646 ms	184064 KB	Output is correct
39	Correct	1171 ms	215892 KB	Output is correct
40	Correct	6242 ms	225408 KB	Output is correct
41	Correct	10965 ms	225408 KB	Output is correct
42	Correct	8735 ms	225408 KB	Output is correct
43	Correct	1302 ms	243580 KB	Output is correct
44	Correct	1387 ms	243580 KB	Output is correct
45	Correct	2730 ms	243580 KB	Output is correct
46	Runtime error	6518 ms	257024 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
47	Halted	0 ms	0 KB	-