Submission #4635

#	Time	Username	Problem	Language	Result	Execution time	Memory
4635		ainta	Game (IOI13_game)	C++98	63 / 100	3736 ms	256000 KiB

game

#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;

int N,M;

struct Y_Seg{
	Y_Seg *c1, *c2;
	int b,e;
	long long G;
	Y_Seg(int p,int q){
		c1=NULL,c2=NULL,G=0;
		b=p,e=q;
	}
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	int b,e;
	X_Seg(int p,int q){
		c1=NULL,c2=NULL,cy=NULL;
		b=p,e=q;
	}
};
X_Seg *root;

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

void init(int R, int C) {
	N=R,M=C;
	root = new X_Seg(0,N-1);
}

void update_Y(Y_Seg *node, int y, long long K){
	if(node->b==node->e){
		node->G=K;
		return;
	}
	int m = (node->b+node->e)>>1;

	node->G=0;
	if(m >= y){
		if(!node->c1)node->c1 = new Y_Seg(node->b,m);
		update_Y(node->c1, y, K);
	}
	else{
		if(!node->c2)node->c2 = new Y_Seg(m+1,node->e);
		update_Y(node->c2, y, K);
	}
	node->G=gcd2(node->c1?node->c1->G:0,node->c2?node->c2->G:0);
}

void update_XY(X_Seg *node, int y){
	Y_Seg *n1=node->c1?node->c1->cy:NULL, *n2=node->c2?node->c2->cy:NULL, *cur=node->cy;
	int m;
	while(n1 || n2){
		cur->G = gcd2(n1?n1->G:0,n2?n2->G:0);
		if(cur->b==cur->e)break;
		m=(cur->b+cur->e)>>1;
		if(m>=y){
			if(!cur->c1)cur->c1=new Y_Seg(cur->b,m);
			cur=cur->c1;
			if(n1)n1=n1->c1;
			if(n2)n2=n2->c1;
		}
		else{
			if(!cur->c2)cur->c2=new Y_Seg(m+1,cur->e);
			cur=cur->c2;
			if(n1)n1=n1->c2;
			if(n2)n2=n2->c2;
		}
	}
}

void update_X(X_Seg *node, int x, int y, long long K){
	if(node->b==node->e){
		if(node->cy==NULL)node->cy = new Y_Seg(0,M-1);
		update_Y(node->cy, y, K);
		return;
	}
	int m = (node->b+node->e)>>1;

	if(!node->cy)node->cy = new Y_Seg(0,M-1);
	if(m >= x){
		if(!node->c1)node->c1 = new X_Seg(node->b,m);
		update_X(node->c1, x, y, K);
	}
	else{
		if(!node->c2)node->c2 = new X_Seg(m+1,node->e);
		update_X(node->c2, x, y, K);
	}

	update_XY(node, y);
}

void update(int P, int Q, long long K) {
	update_X(root,P,Q,K);
}

long long CalcY(Y_Seg *node, int s,int l){
	if(s==node->b && l==node->e){
		return node->G;
	}
	int m = (node->b + node->e) >>1;
	long long G=0;
	if(s <= m){
		if(node->c1){
			G=CalcY(node->c1,s,min(l,m));
		}
	}
	if(l > m){
		if(node->c2){
			G=gcd2(G,CalcY(node->c2,max(m+1,s),l));
		}
	}
	return G;
}

long long CalcX(X_Seg *node, int P,int Q,int U,int V){
	if(P==node->b && U==node->e){
		if(node->cy)return CalcY(node->cy,Q,V);
		return 0;
	}
	int m = (node->b + node->e) >>1;
	long long G=0;
	if(P <= m){
		if(node->c1){
			G=CalcX(node->c1,P,Q,min(U,m),V);
		}
	}
	if(U > m){
		if(node->c2){
			G=gcd2(G,CalcX(node->c2,max(m+1,P),Q,U,V));
		}
	}
	return G;
}

long long calculate(int P, int Q, int U, int V) {
	return CalcX(root,P,Q,U,V);
}

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