oj.uz

Submission #64699

# Submission time Handle Problem Language Result Execution time Memory
64699 2018-08-05T12:21:37 Z TadijaSebez Game (IOI13_game) C++11
80 / 100
 10965 ms 257024 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -