oj.uz

Submission #4635

# Submission time Handle Problem Language Result Execution time Memory
4635 2013-11-13T11:55:12 Z ainta Game (IOI13_game) C++
63 / 100
 3736 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;

	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1340 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 1340 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 880 ms 13616 KB Output is correct
5 Correct 532 ms 13616 KB Output is correct
6 Correct 808 ms 13880 KB Output is correct
7 Correct 920 ms 13880 KB Output is correct
8 Correct 556 ms 8336 KB Output is correct
9 Correct 876 ms 13880 KB Output is correct
10 Correct 748 ms 13880 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 1340 KB Output is correct
3 Correct 0 ms 1340 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 1340 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 1396 ms 18368 KB Output is correct
13 Correct 3144 ms 8864 KB Output is correct
14 Correct 392 ms 1340 KB Output is correct
15 Correct 3736 ms 12692 KB Output is correct
16 Correct 288 ms 26948 KB Output is correct
17 Correct 1412 ms 15992 KB Output is correct
18 Correct 2316 ms 26948 KB Output is correct
19 Correct 2008 ms 26948 KB Output is correct
20 Correct 1828 ms 26948 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 1340 KB Output is correct
3 Correct 0 ms 1340 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 1340 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 868 ms 13616 KB Output is correct
13 Correct 528 ms 13616 KB Output is correct
14 Correct 804 ms 13880 KB Output is correct
15 Correct 876 ms 13880 KB Output is correct
16 Correct 560 ms 8336 KB Output is correct
17 Correct 860 ms 13880 KB Output is correct
18 Correct 724 ms 13880 KB Output is correct
19 Correct 1368 ms 18368 KB Output is correct
20 Correct 3120 ms 8864 KB Output is correct
21 Correct 392 ms 1340 KB Output is correct
22 Correct 3728 ms 12692 KB Output is correct
23 Correct 276 ms 26948 KB Output is correct
24 Correct 1408 ms 15992 KB Output is correct
25 Correct 2284 ms 26948 KB Output is correct
26 Correct 1992 ms 26948 KB Output is correct
27 Correct 1852 ms 26948 KB Output is correct
28 Memory limit exceeded 736 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 1340 KB Output is correct
3 Correct 0 ms 1340 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 1340 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 892 ms 13616 KB Output is correct
13 Correct 508 ms 13616 KB Output is correct
14 Correct 784 ms 13880 KB Output is correct
15 Correct 872 ms 13880 KB Output is correct
16 Correct 560 ms 8336 KB Output is correct
17 Correct 852 ms 13880 KB Output is correct
18 Correct 736 ms 13880 KB Output is correct
19 Correct 1372 ms 18368 KB Output is correct
20 Correct 3128 ms 8864 KB Output is correct
21 Correct 388 ms 1340 KB Output is correct
22 Correct 3708 ms 12692 KB Output is correct
23 Correct 292 ms 26948 KB Output is correct
24 Correct 1388 ms 15992 KB Output is correct
25 Correct 2300 ms 26948 KB Output is correct
26 Correct 1972 ms 26948 KB Output is correct
27 Correct 1816 ms 26948 KB Output is correct
28 Memory limit exceeded 712 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -