Submission #4617

#	Time	Username	Problem	Language	Result	Execution time	Memory
4617		cki86201	Game (IOI13_game)	C++98	36 / 100	4416 ms	132416 KiB

game

#include "game.h"

//36point;

const int idx = 2048;
typedef long long ll;

bool flag;
ll T[4100][4100];

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

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 update(int P, int Q, long long 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;
}

long long calculate(int P, int Q, int U, int 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: 0 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20