Submission #30026

#	Time	Username	Problem	Language	Result	Execution time	Memory
30026		PrOAhMeT	Game (IOI13_game)	C++14	100 / 100	10193 ms	218584 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXR=1e9,MAXC=1e9;
const int MAX1=40*22000,MAX2=20*20*22000;

int root[MAX1],cl2[MAX2],cr2[MAX2],l2[MAX2],r2[MAX2];
int cl1[MAX1],cr1[MAX1],tme1,tme2,ROOT;
LL f[MAX2];

long long gcd2(long long X, long long Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int newNode1() {

	int v=++tme1;
	root[tme1]=++tme2;
	l2[tme2]=0; r2[tme2]=MAXC-1;
	return v;

}

int newNode2(int l,int r) {

	int v=++tme2;
	l2[v]=l; r2[v]=r;
	return v;

}

void init(int r,int c) {

	ROOT=newNode1();

}

LL que2(int x,int l,int r) {

	if(x==0||l2[x]>r||r2[x]<l) 
		return 0; 
	if(l2[x]>=l&&r2[x]<=r)
		return f[x];
	return gcd2(que2(cl2[x],l,r),que2(cr2[x],l,r));

}

LL que1(int x,int l,int r,int ll,int rr,int xx,int yy) {

	if(l>rr||r<ll||x==0)
		return 0;
	if(l>=ll&&r<=rr)
		return que2(root[x],xx,yy);
	int md=(l+r)/2;
	return gcd2(que1(cl1[x],l,md,ll,rr,xx,yy),que1(cr1[x],md+1,r,ll,rr,xx,yy));

}

void upd2(int x,int y,LL k) {
	//cout<<"upd2: "<<x<<" "<<l2[x]<<" "<<r2[x]<<endl;
	if(l2[x]==y&&r2[x]==y) {
		f[x]=k;
		return;
	}
	int mdo=(l2[x]+r2[x])/2;
	int &v=(y<=mdo?cl2[x]:cr2[x]);
	if(v==0) {
		v=newNode2(y,y);
		f[v]=k;
	}
	else if(l2[v]<=y&&r2[v]>=y) 
		upd2(v,y,k);
	else {
		//cout<<"oh no "<<l2[v]<<" "<<r2[v]<<" "<<y<<endl;
		int l=l2[x],r=r2[x],md=(l2[x]+r2[x])/2,t=v;
		do {
			if(y<=md) 
				r=md;
			else l=md+1;
			md=(l+r)/2;
		} while((y<=md)==(l2[v]<=md));
		//cout<<l<<" "<<r<<endl;
		int nw=newNode2(l,r);
		v=nw;
		if(l2[t]<=md) cl2[nw]=t;
		else cr2[nw]=t;
		upd2(nw,y,k);
	}
	f[x]=gcd2(f[cl2[x]],f[cr2[x]]);

}

void upd1(int &x,int l,int r,int ll,int y,LL k) {

	if(x==0) 
		x=newNode1();
	if(l==r) {
		upd2(root[x],y,k);
		return;
	}
	int md=(l+r)/2;
	if(ll<=md)
		upd1(cl1[x],l,md,ll,y,k);
	else upd1(cr1[x],md+1,r,ll,y,k);
	upd2(root[x],y,gcd2(que2(root[cl1[x]],y,y),que2(root[cr1[x]],y,y)));

}

void update(int x,int y,LL k) {

	upd1(ROOT,0,MAXR-1,x,y,k);

}

LL calculate(int p,int q,int u,int v) {

	return que1(ROOT,0,MAXR-1,p,u,q,v);

}

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;
      ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20