oj.uz

답안 #4621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4621 2013-11-11T11:25:44 Z cki86201 게임 (IOI13_game) C++
0 / 100
 0 ms 1108 KB 
#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,m+1,d);
		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),s,m);
		}
		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),m+1,d);
		}
	}
	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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Incorrect 0 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Incorrect 0 ms 1108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Incorrect 0 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Incorrect 0 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Incorrect 0 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -