Submission #4618

#	Time	Username	Problem	Language	Result	Execution time	Memory
4618		cki86201	Game (IOI13_game)	C++98	63 / 100	4416 ms	152728 KiB

game

#include "game.h"

//63point;

const int idx = 2048;
const int idx2 = 131072;
typedef long long ll;

int flag;
ll T[4100][4100];
ll T2[10][260000];

ll gc(ll x,ll y){
	ll tmp=-1;
	while(x!=tmp&&y)tmp=x,x=y,y=tmp%y;
	return x;
}

void init(int R, int C){
	if(R<=2000&&C<=2000)flag=1;
	else if(R<=10&&C<=100000)flag=2;
	else flag=3;
}

void upd1(int x,int y,ll K)
{
	int y1=y+idx;
	T[x][y1]=gc(T[x<<1][y1],T[x<<1|1][y1]);
	y1>>=1;
	while(y1){
		T[x][y1]=gc(T[x][y1<<1],T[x][y1<<1|1]);
		y1>>=1;
	}
}

void update2(int x,int y,ll item)
{
	y+=idx2;
	T2[x][y]=item;
	y>>=1;
	while(y){
		T2[x][y]=gc(T2[x][y<<1],T2[x][y<<1|1]);
		y>>=1;
	}
}

void update(int P, int Q, long long K){
	if(flag==3)return;
	if(flag==2)update2(P,Q,K);
	int p=P+idx,q=Q+idx;
	T[p][q]=K;q>>=1;
	while(q){T[p][q]=gc(T[p][q<<1],T[p][q<<1|1]);q>>=1;}
	p>>=1;
	while(p){
		upd1(p,Q,K);
		p>>=1;
	}
}

ll cal1(int p,int s,int d)
{
	int s1=s+idx,d1=d+idx;
	ll ret=0;
	while(s1<=d1){
		ret=gc(ret,T[p][s1]);
		ret=gc(ret,T[p][d1]);
		s1=(s1+1)>>1;
		d1=(d1-1)>>1;
	}
	return ret;
}

ll read2(int t,int x,int y)
{
	ll ret=0;
	x+=idx2,y+=idx2;
	while(x<=y){
		ret=gc(ret,T2[t][x]);
		ret=gc(ret,T2[t][y]);
		x=(x+1)>>1;
		y=(y-1)>>1;
	}
	return ret;
}

ll calculate2(int P, int Q, int U, int V){
	ll ret=0;
	for(int i=P;i<=U;i++)ret=gc(ret,read2(i,Q,V));
	return ret;
}

ll calculate(int P, int Q, int U, int V){
	if(flag==3)return -1;
	if(flag==2)return calculate2(P,Q,U,V);
	int p=P+idx,q=U+idx;
	ll ret=0;
	while(p<=q){
		ret=gc(ret,cal1(p,Q,V));
		ret=gc(ret,cal1(q,Q,V));
		p=(p+1)>>1;
		q=(q-1)>>1;
	}
	return ret;
}

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