oj.uz

Submission #4622

# Submission time Handle Problem Language Result Execution time Memory
4622 2013-11-11T11:26:38 Z cki86201 Game (IOI13_game) C++
63 / 100
 3060 ms 256000 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,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),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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 0 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 0 ms 1108 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct
12 Correct 0 ms 1108 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 832 ms 9292 KB Output is correct
5 Correct 592 ms 9292 KB Output is correct
6 Correct 756 ms 9556 KB Output is correct
7 Correct 840 ms 9556 KB Output is correct
8 Correct 540 ms 5860 KB Output is correct
9 Correct 800 ms 9556 KB Output is correct
10 Correct 712 ms 9556 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 0 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 0 ms 1108 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct
12 Correct 1356 ms 12460 KB Output is correct
13 Correct 2624 ms 6124 KB Output is correct
14 Correct 360 ms 1108 KB Output is correct
15 Correct 3048 ms 8632 KB Output is correct
16 Correct 308 ms 18136 KB Output is correct
17 Correct 1284 ms 10876 KB Output is correct
18 Correct 2024 ms 18136 KB Output is correct
19 Correct 1784 ms 18136 KB Output is correct
20 Correct 1696 ms 18136 KB Output is correct
21 Correct 0 ms 1108 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 0 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 0 ms 1108 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct
12 Correct 836 ms 9292 KB Output is correct
13 Correct 588 ms 9292 KB Output is correct
14 Correct 740 ms 9556 KB Output is correct
15 Correct 804 ms 9556 KB Output is correct
16 Correct 540 ms 5860 KB Output is correct
17 Correct 784 ms 9556 KB Output is correct
18 Correct 728 ms 9556 KB Output is correct
19 Correct 1380 ms 12460 KB Output is correct
20 Correct 2648 ms 6124 KB Output is correct
21 Correct 352 ms 1108 KB Output is correct
22 Correct 3060 ms 8632 KB Output is correct
23 Correct 284 ms 18136 KB Output is correct
24 Correct 1264 ms 10876 KB Output is correct
25 Correct 1992 ms 18136 KB Output is correct
26 Correct 1780 ms 18136 KB Output is correct
27 Correct 1712 ms 18136 KB Output is correct
28 Correct 1128 ms 248476 KB Output is correct
29 Memory limit exceeded 2480 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 0 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 0 ms 1108 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct
12 Correct 836 ms 9292 KB Output is correct
13 Correct 580 ms 9292 KB Output is correct
14 Correct 716 ms 9556 KB Output is correct
15 Correct 812 ms 9556 KB Output is correct
16 Correct 556 ms 5860 KB Output is correct
17 Correct 788 ms 9556 KB Output is correct
18 Correct 724 ms 9556 KB Output is correct
19 Correct 1364 ms 12460 KB Output is correct
20 Correct 2644 ms 6124 KB Output is correct
21 Correct 344 ms 1108 KB Output is correct
22 Correct 3024 ms 8632 KB Output is correct
23 Correct 292 ms 18136 KB Output is correct
24 Correct 1256 ms 10876 KB Output is correct
25 Correct 2044 ms 18136 KB Output is correct
26 Correct 1744 ms 18136 KB Output is correct
27 Correct 1648 ms 18136 KB Output is correct
28 Correct 1136 ms 248476 KB Output is correct
29 Memory limit exceeded 2440 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -