Submission #64709

#	Time	Username	Problem	Language	Result	Execution time	Memory
64709		TadijaSebez	Game (IOI13_game)	C++11	100 / 100	11473 ms	166748 KiB

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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20