Submission #4624

#	Time	Username	Problem	Language	Result	Execution time	Memory
4624		cki86201	Game (IOI13_game)	C++98	100 / 100	8452 ms	76316 KiB

game

#include "game.h"
#include<stdlib.h>

typedef long long ll;

int R,C;

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

struct node1{
	node1(){}
	node1(int s,int d,ll x):s(s),d(d),x(x),right(0),left(0){}
	int s,d;
	ll x;
	node1 *right,*left;
};

struct node2{
	node1 *x;
	node2 *right,*left;
}*tree;

void init(int R, int C){
	::R=R,::C=C;
	tree = new node2();
}

void update1(node1 *R,int u,ll K)
{
	int s = R->s,d = R->d;
	if(s == d){R->x = K;return;}
	int m = (s+d)>>1;
	node1 **t = &(u<=m?R->left:R->right);
	if(*t==NULL)*t = new node1(u,u,K);
	else if((*t)->s<=u && u<=(*t)->d)update1(*t,u,K);
	else{
		while((u>m) ^ ((*t)->s<=m)){
			if(u<=m)d=m;
			else s=m+1;
			m=(s+d)>>1;
		}
		node1 *n = new node1(s,d,0);
		if((*t)->s<=m)n->left = *t;
		else n->right = *t;
		*t = n;
		update1(n,u,K);
	}
	R->x = gc(R->left?R->left->x:0,R->right?R->right->x:0);
}

ll read1(node1 *R,int l,int r)
{
	if(!R)return 0;
	int s = R->s, d = R->d;
	if(d<l||r<s)return 0;
	if(l<=s&&d<=r)return R->x;
	return gc(R->left?read1(R->left,l,r):0,R->right?read1(R->right,l,r):0);
}

void update2(node2 *R,int u1,int u2,int s,int d,ll K)
{
	if(s==d){
		if(!R->x)R->x = new node1(1,C,0);
		update1(R->x,u2,K);
		return;
	}
	int m = (s+d)>>1;
	if(u1<=m){
		if(!R->left)R->left = new node2();
		update2(R->left,u1,u2,s,m,K);
	}
	else{
		if(!R->right)R->right =new node2();
		update2(R->right,u1,u2,m+1,d,K);
	}
	ll L = gc((R->left)?read1(R->left->x,u2,u2):0,(R->right)?read1(R->right->x,u2,u2):0);
	if(!R->x)R->x = new node1(1,C,0);
	update1(R->x,u2,L);
}

ll read2(node2 *R,int l1,int r1,int l2,int r2,int s,int d)
{
	int m = (s+d)>>1;
	if(l1<=s&&d<=r1)return read1(R->x,l2,r2);
	if(r1<s||d<l1)return 0;
	return gc((R->left)?read2(R->left,l1,r1,l2,r2,s,m):0,(R->right)?read2(R->right,l1,r1,l2,r2,m+1,d):0);
}

void update(int P, int Q, ll K){
	++P,++Q;
	update2(tree,P,Q,1,R,K);
}

ll calculate(int P, int Q, int U, int V){
	++P,++Q,++U,++V;
	return read2(tree,P,U,Q,V,1,R);
}

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