oj.uz

Submission #4634

# Submission time Handle Problem Language Result Execution time Memory
4634 2013-11-13T11:50:14 Z ainta Game (IOI13_game) C++
0 / 100
 0 ms 1472 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;

	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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Incorrect 0 ms 1472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.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 Incorrect 0 ms 1208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Incorrect 0 ms 1472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Incorrect 0 ms 1472 KB Output isn't correct
3 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 Incorrect 0 ms 1472 KB Output isn't correct
3 Halted 0 ms 0 KB -