Submission #400311

#	Time	Username	Problem	Language	Result	Execution time	Memory
400311		Jasiekstrz	Game (IOI13_game)	C++17	100 / 100	6588 ms	245156 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int D=4;
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* son[D];
	TreeC()
	{
		val=0;
		for(int i=0;i<D;i++)
			son[i]=NULL;
	}
	~TreeC()
	{
		for(int i=0;i<D;i++)
			delete son[i];
	}
	void add(int l,int r,int x,long long c)
	{
		if(l==r)
		{
			val=c;
			return;
		}
		val=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
		{
			if(j<=x && x<j+d)
			{
				if(son[i]==NULL)
					son[i]=new TreeC;
				son[i]->add(j,j+d-1,x,c);
			}
			val=gcd2(val, (son[i]==NULL ? 0:son[i]->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;
		long long ans=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
			ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs)));
		return ans;
	}
};
struct TreeR
{
	TreeC *t;
	TreeR* son[D];
	TreeR()
	{
		t=new TreeC;
		for(int i=0;i<D;i++)
			son[i]=NULL;
	}
	~TreeR()
	{
		delete t;
		for(int i=0;i<D;i++)
			delete son[i];
	}
	void add(int l,int r,int x,int y,long long c)
	{
		if(l==r)
		{
			t->add(0,cc,y,c);
			return;
		}
		long long tmp=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
		{
			if(j<=x && x<j+d)
			{
				if(son[i]==NULL)
					son[i]=new TreeR;
				son[i]->add(j,j+d-1,x,y,c);
			}
			tmp=gcd2(tmp, (son[i]==NULL ? 0:son[i]->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);
		long long ans=0;
		int d=(r-l+1)/D;
		for(int i=0,j=l;i<D;i++,j+=d)
			ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs,ly,ry)));
		return ans;
	}
};
TreeR* root;
void init(int R,int C)
{
	for(rr=1;rr<R;rr*=D);
	rr--;
	for(cc=1;cc<C;cc*=D);
	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: 17 / 17
• Subtask 5: 20 / 20