oj.uz

Submission #4631

# Submission time Handle Problem Language Result Execution time Memory
4631 2013-11-13T11:32:12 Z ainta Game (IOI13_game) C++
63 / 100
 3660 ms 256000 KB 
#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;

	if(!node->c1)node->c1 = new Y_Seg(node->b,m);
	if(!node->c2)node->c2 = new Y_Seg(m+1,node->e);
	
	if(m < y)update_Y(node->c2, y, K);
	else update_Y(node->c1, y, K);

	node->G=gcd2(node->c1->G,node->c2->G);
}

void update_XY(X_Seg *node, int y){
	Y_Seg *n1=node->c1->cy, *n2=node->c2->cy, *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(!cur->c1)cur->c1=new Y_Seg(cur->b,m);
		if(!cur->c2)cur->c2=new Y_Seg(m+1,cur->e);
		if(m>=y){
			cur=cur->c1;
			if(n1)n1=n1->c1;
			if(n2)n2=n2->c1;
		}
		else{
			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->c1)node->c1 = new X_Seg(node->b,m);
	if(!node->c2)node->c2 = new X_Seg(m+1,node->e);
	if(!node->cy)node->cy = new Y_Seg(0,M-1);

	if(m < x)update_X(node->c2, x, y, K);
	else update_X(node->c1, 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.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 968 ms 22064 KB Output is correct
5 Correct 572 ms 22064 KB Output is correct
6 Correct 844 ms 22592 KB Output is correct
7 Correct 940 ms 22592 KB Output is correct
8 Correct 600 ms 13484 KB Output is correct
9 Correct 920 ms 22592 KB Output is correct
10 Correct 816 ms 22460 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1472 KB Output is correct
3 Correct 0 ms 1472 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1472 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1480 ms 28268 KB Output is correct
13 Correct 3064 ms 12560 KB Output is correct
14 Correct 444 ms 1472 KB Output is correct
15 Correct 3648 ms 19028 KB Output is correct
16 Correct 300 ms 43712 KB Output is correct
17 Correct 1652 ms 26156 KB Output is correct
18 Correct 2512 ms 43712 KB Output is correct
19 Correct 2276 ms 43844 KB Output is correct
20 Correct 2124 ms 43712 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1472 KB Output is correct
3 Correct 0 ms 1472 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1472 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 952 ms 22064 KB Output is correct
13 Correct 596 ms 22064 KB Output is correct
14 Correct 832 ms 22592 KB Output is correct
15 Correct 916 ms 22592 KB Output is correct
16 Correct 624 ms 13484 KB Output is correct
17 Correct 912 ms 22592 KB Output is correct
18 Correct 788 ms 22460 KB Output is correct
19 Correct 1464 ms 28268 KB Output is correct
20 Correct 3012 ms 12560 KB Output is correct
21 Correct 420 ms 1472 KB Output is correct
22 Correct 3660 ms 19028 KB Output is correct
23 Correct 332 ms 43712 KB Output is correct
24 Correct 1540 ms 26156 KB Output is correct
25 Correct 2508 ms 43712 KB Output is correct
26 Correct 2208 ms 43844 KB Output is correct
27 Correct 2092 ms 43712 KB Output is correct
28 Memory limit exceeded 512 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1472 KB Output is correct
3 Correct 0 ms 1472 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1472 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 896 ms 22064 KB Output is correct
13 Correct 576 ms 22064 KB Output is correct
14 Correct 816 ms 22592 KB Output is correct
15 Correct 920 ms 22592 KB Output is correct
16 Correct 588 ms 13484 KB Output is correct
17 Correct 896 ms 22592 KB Output is correct
18 Correct 820 ms 22460 KB Output is correct
19 Correct 1468 ms 28268 KB Output is correct
20 Correct 3044 ms 12560 KB Output is correct
21 Correct 428 ms 1472 KB Output is correct
22 Correct 3644 ms 19028 KB Output is correct
23 Correct 324 ms 43712 KB Output is correct
24 Correct 1608 ms 26156 KB Output is correct
25 Correct 2560 ms 43712 KB Output is correct
26 Correct 2232 ms 43844 KB Output is correct
27 Correct 2052 ms 43712 KB Output is correct
28 Memory limit exceeded 408 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -