oj.uz

Submission #64696

# Submission time Handle Problem Language Result Execution time Memory
64696 2018-08-05T12:19:05 Z TadijaSebez Game (IOI13_game) C++11
80 / 100
 6055 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 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 4 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 608 KB Output is correct
12 Correct 3 ms 608 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 3 ms 608 KB Output is correct
3 Correct 3 ms 660 KB Output is correct
4 Correct 1394 ms 10980 KB Output is correct
5 Correct 448 ms 15220 KB Output is correct
6 Correct 1090 ms 16792 KB Output is correct
7 Correct 1356 ms 21068 KB Output is correct
8 Correct 721 ms 25268 KB Output is correct
9 Correct 1262 ms 30188 KB Output is correct
10 Correct 1480 ms 34548 KB Output is correct
11 Correct 2 ms 34548 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34548 KB Output is correct
2 Correct 3 ms 34548 KB Output is correct
3 Correct 3 ms 34548 KB Output is correct
4 Correct 3 ms 34548 KB Output is correct
5 Correct 3 ms 34548 KB Output is correct
6 Correct 2 ms 34548 KB Output is correct
7 Correct 3 ms 34548 KB Output is correct
8 Correct 2 ms 34548 KB Output is correct
9 Correct 3 ms 34548 KB Output is correct
10 Correct 2 ms 34548 KB Output is correct
11 Correct 3 ms 34548 KB Output is correct
12 Correct 2180 ms 45260 KB Output is correct
13 Correct 4376 ms 45260 KB Output is correct
14 Correct 483 ms 45516 KB Output is correct
15 Correct 4749 ms 54340 KB Output is correct
16 Correct 472 ms 59864 KB Output is correct
17 Correct 1837 ms 62464 KB Output is correct
18 Correct 3166 ms 70280 KB Output is correct
19 Correct 2847 ms 75964 KB Output is correct
20 Correct 2766 ms 80852 KB Output is correct
21 Correct 3 ms 80852 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 80852 KB Output is correct
2 Correct 4 ms 80852 KB Output is correct
3 Correct 4 ms 80852 KB Output is correct
4 Correct 3 ms 80852 KB Output is correct
5 Correct 3 ms 80852 KB Output is correct
6 Correct 4 ms 80852 KB Output is correct
7 Correct 3 ms 80852 KB Output is correct
8 Correct 2 ms 80852 KB Output is correct
9 Correct 3 ms 80852 KB Output is correct
10 Correct 3 ms 80852 KB Output is correct
11 Correct 3 ms 80852 KB Output is correct
12 Correct 1278 ms 84528 KB Output is correct
13 Correct 439 ms 88388 KB Output is correct
14 Correct 1081 ms 88880 KB Output is correct
15 Correct 1456 ms 93328 KB Output is correct
16 Correct 790 ms 97260 KB Output is correct
17 Correct 1401 ms 102476 KB Output is correct
18 Correct 1478 ms 106636 KB Output is correct
19 Correct 2283 ms 117420 KB Output is correct
20 Correct 4397 ms 117420 KB Output is correct
21 Correct 465 ms 117740 KB Output is correct
22 Correct 5323 ms 126496 KB Output is correct
23 Correct 540 ms 132152 KB Output is correct
24 Correct 1915 ms 134584 KB Output is correct
25 Correct 3935 ms 142532 KB Output is correct
26 Correct 3265 ms 147708 KB Output is correct
27 Correct 3493 ms 152228 KB Output is correct
28 Correct 901 ms 177752 KB Output is correct
29 Correct 3332 ms 190004 KB Output is correct
30 Correct 6055 ms 190004 KB Output is correct
31 Correct 5042 ms 192120 KB Output is correct
32 Correct 876 ms 192120 KB Output is correct
33 Correct 1113 ms 196596 KB Output is correct
34 Correct 619 ms 223220 KB Output is correct
35 Correct 2088 ms 223220 KB Output is correct
36 Correct 5680 ms 241132 KB Output is correct
37 Correct 4019 ms 250020 KB Output is correct
38 Correct 4643 ms 250336 KB Output is correct
39 Correct 2935 ms 250336 KB Output is correct
40 Correct 4 ms 250336 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 250336 KB Output is correct
2 Correct 3 ms 250336 KB Output is correct
3 Correct 4 ms 250336 KB Output is correct
4 Correct 3 ms 250336 KB Output is correct
5 Correct 3 ms 250336 KB Output is correct
6 Correct 3 ms 250336 KB Output is correct
7 Correct 3 ms 250336 KB Output is correct
8 Correct 4 ms 250336 KB Output is correct
9 Correct 4 ms 250336 KB Output is correct
10 Correct 3 ms 250336 KB Output is correct
11 Correct 4 ms 250336 KB Output is correct
12 Correct 1330 ms 250336 KB Output is correct
13 Correct 503 ms 250336 KB Output is correct
14 Correct 1281 ms 250336 KB Output is correct
15 Correct 1306 ms 250336 KB Output is correct
16 Correct 797 ms 250336 KB Output is correct
17 Correct 1355 ms 250780 KB Output is correct
18 Correct 1393 ms 253800 KB Output is correct
19 Runtime error 1986 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.
20 Halted 0 ms 0 KB -