제출 #4619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4619		cki86201	게임 (IOI13_game)	C++98	0 / 100	0 ms	1108 KiB

game

#include "game.h"
#include<stdlib.h>
//for 80point;

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{
	ll x;
	node1 *left,*right;
	void update(int u,int s,int d,ll K){
		if(s==d){x=K;return;}
		int m=(s+d)>>1;
		if(u<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			left->update(u,s,m,K);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			right->update(u,m+1,d,K);
		}
		if(right&&left)x=gc(right->x,left->x);
		else if(right)x=right->x;
		else x=left->x;
	}
	ll read(int l,int r,int s,int d){
		if(l<=s&&d<=r)return x;
		if(r<s||d<l)return 0;
		int m=(s+d)>>1;
		if(right&&left)return gc(left->read(l,r,s,m),right->read(l,r,m+1,d));
		if(right)return right->read(l,r,m+1,d);
		if(left)return left->read(l,r,s,m);
		return 0;
	}
	void Union(int r,node1 A,node1 B,int s,int d){
		x=gc(A.x,B.x);
		if(s==d)return;
		int m=(s+d)>>1;
		if(r<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			if(A.left&&B.left)left->Union(r,*(A.left),*(B.left),s,m);
			else if(A.left)left->Copy(r,*(A.left),s,m);
			else left->Copy(r,*(B.left),m+1,d);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			if(A.right&&B.right)right->Union(r,*(A.right),*(B.right),m+1,d);
			else if(A.right)right->Copy(r,*(A.right),m+1,d);
			else right->Copy(r,*(B.right),s,m);
		}
	}
	void Copy(int r,node1 A,int s,int d){
		if(s==d){x=A.x;return;}
		int m=(s+d)>>1;
		if(r<=m){
			if(!left)left=(node1 *)calloc(1,sizeof(node1));
			left->Copy(r,*(A.left),s,m);
		}
		else{
			if(!right)right=(node1 *)calloc(1,sizeof(node1));
			right->Copy(r,*(A.right),m+1,d);
		}
		if(right&&left)x=gc(right->x,left->x);
		else if(right)x=right->x;
		else x=left->x;
	}
};

struct node2{
	node1 x;
	node2 *left,*right;
	void update(int u1,int u2,int s,int d,ll K){
		if(s==d){x.update(u2,1,C,K);return;}
		int m=(s+d)>>1;
		if(u1<=m){
			if(!left)left=(node2 *)calloc(1,sizeof(node2));
			left->update(u1,u2,s,m,K);
		}
		else{
			if(!right)right=(node2 *)calloc(1,sizeof(node2));
			right->update(u1,u2,m+1,d,K);
		}
		if(right&&left)x.Union(u2,right->x,left->x,1,C);
		else if(right)x.Copy(u2,right->x,1,C);
		else if(left)x.Copy(u2,left->x,1,C);
	}
	ll read(int l1,int r1,int l2,int r2,int s,int d){
		if(l1<=s&&d<=r1)return x.read(l2,r2,1,C);
		if(r1<s||d<l1)return 0;
		int m=(s+d)>>1;
		if(right&&left)return gc(left->read(l1,r1,l2,r2,s,m),right->read(l1,r1,l2,r2,m+1,d));
		if(right)return right->read(l1,r1,l2,r2,m+1,d);
		if(left)return left->read(l1,r1,l2,r2,s,m);
		return 0;
	}
}tree;

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

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

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

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