Submission #400264

#	Time	Username	Problem	Language	Result	Execution time	Memory
400264		Jasiekstrz	Game (IOI13_game)	C++17	63 / 100	3065 ms	256004 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;
long long gcd2(long long X,long long Y) 
{
    long long tmp;
    while(X!=Y && Y!=0)
	{
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}
int rr,cc;
struct TreeC
{
	long long val;
	TreeC *lson,*rson;
	TreeC()
	{
		val=0;
		lson=NULL;
		rson=NULL;
	}
	~TreeC()
	{
		delete lson;
		delete rson;
	}
	void mkchildren()
	{
		if(lson==NULL)
			lson=new TreeC;
		if(rson==NULL)
			rson=new TreeC;
		return;
	}
	void add(int l,int r,int x,long long c)
	{
		if(l==r)
		{
			val=c;
			return;
		}
		mkchildren();
		int mid=(l+r)/2;
		if(x<=mid)
			lson->add(l,mid,x,c);
		else
			rson->add(mid+1,r,x,c);
		val=gcd2(lson->val,rson->val);
		return;
	}
	long long read(int l,int r,int ls,int rs)
	{
		if(rs<l || r<ls)
			return 0;
		if(ls<=l && r<=rs)
			return val;
		mkchildren();
		int mid=(l+r)/2;
		return gcd2(lson->read(l,mid,ls,rs),rson->read(mid+1,r,ls,rs));
	}
};
struct TreeR
{
	TreeC *t;
	TreeR *lson,*rson;
	TreeR()
	{
		t=new TreeC;
		lson=NULL;
		rson=NULL;
	}
	~TreeR()
	{
		delete t;
		delete lson;
		delete rson;
	}
	void mkchildren()
	{
		if(lson==NULL)
			lson=new TreeR;
		if(rson==NULL)
			rson=new TreeR;
		return;
	}
	void add(int l,int r,int x,int y,long long c)
	{
		if(l==r)
		{
			t->add(0,cc,y,c);
			return;
		}
		int mid=(l+r)/2;
		mkchildren();
		if(x<=mid)
			lson->add(l,mid,x,y,c);
		else
			rson->add(mid+1,r,x,y,c);
		long long tmp=gcd2(lson->t->read(0,cc,y,y),rson->t->read(0,cc,y,y));
		t->add(0,cc,y,tmp);
		return;
	}
	long long read(int l,int r,int ls,int rs,int ly,int ry)
	{
		if(rs<l || r<ls)
			return 0;
		if(ls<=l && r<=rs)
			return t->read(0,cc,ly,ry);
		mkchildren();
		int mid=(l+r)/2;
		return gcd2(lson->read(l,mid,ls,rs,ly,ry),rson->read(mid+1,r,ls,rs,ly,ry));
	}
};
TreeR* root;
void init(int R,int C)
{
	for(rr=1;rr<R;rr*=2);
	rr--;
	for(cc=1;cc<C;cc*=2);
	cc--;
	root=new TreeR;
	return;
}
void update(int P,int Q,long long K)
{
	root->add(0,rr,P,Q,K);
	return;
}
long long calculate(int P,int Q,int U,int V)
{
	return root->read(0,rr,P,U,Q,V);
}

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