Submission #18982

#	Time	Username	Problem	Language	Result	Execution time	Memory
18982		suhgyuho_william	Game (IOI13_game)	C++98	63 / 100	2550 ms	256000 KiB

game

#include "game.h"
#include <stdio.h>
#include <stdlib.h>

#define lld long long

long long gcd2(long long X, long long Y) {
    long long tmp;

	if(X == 0) return Y;
	if(Y == 0) return X;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct datay{
	lld value;
	datay *left,*right;
	datay(){
		value = 0;
		left = right = NULL;
	}
};

struct datax{
	datax *left,*right;
	datay *yroot;
	datax(){
		left = right = NULL;
	}
}*xroot;

int R,C;
int nr,nc;

void init(int iR, int iC) {
	R = iR; C = iC;
    for(nr = 1; nr < R; nr *= 2);
    for(nc = 1; nc < C; nc *= 2);
    xroot = new datax();
    xroot -> yroot = new datay();
}

lld ans,value;
int findx,findy;
void yupdate1(datay *node,int left,int right){
	if(left == right){
		node -> value = value;
		return;
	}
	int mid = (left+right)/2;
	if(left <= findy && findy <= mid){
		if(node -> left == NULL) node -> left = new datay();
		yupdate1(node->left,left,mid);
	}
	if(mid+1 <= findy && findy <= right){
		if(node -> right == NULL) node -> right = new datay();
		yupdate1(node->right,mid+1,right);
	}
	if(node->left == NULL){
		if(node->right == NULL) node->value = 0;
		else node->value = (node->right)->value;
	}else{
		if(node->right == NULL) node->value = (node->left)->value;
		else node->value = gcd2((node->left)->value,(node->right)->value);
	}
}
void yclear(datay *node,int left,int right){
	node -> value = 0;
    if(left == right) return;
    int mid = (left+right)/2;
    if(left <= findy && findy <= mid){
		if(node -> left == NULL) node -> left = new datay();
		yclear(node->left,left,mid);
    }
    if(mid+1 <= findy && findy <= right){
		if(node -> right == NULL) node -> right = new datay();
		yclear(node->right,mid+1,right);
    }
}
void yupdate2(datay *node,datay *node2,int left,int right){
	node -> value = gcd2(node->value,node2->value);
	if(left == right) return;
	int mid = (left+right)/2;
	if(left <= findy && findy <= mid && node2->left != NULL) yupdate2(node->left,node2->left,left,mid);
	if(mid+1 <= findy && findy <= right && node2->right != NULL) yupdate2(node->right,node2->right,mid+1,right);
}
void xupdate(datax *node,int left,int right){
	if(node -> yroot == NULL) node -> yroot = new datay();
	if(left == right){
		yupdate1(node -> yroot,1,nc);
		return;
	}
    int mid = (left+right)/2;
    if(left <= findx && findx <= mid){
		if(node -> left == NULL) node -> left = new datax();
        xupdate(node->left,left,mid);
    }
    if(mid+1 <= findx && findx <= right){
		if(node -> right == NULL) node -> right = new datax();
		xupdate(node->right,mid+1,right);
    }
    yclear(node->yroot,1,nc);
    if(node -> left != NULL) yupdate2(node->yroot,(node->left)->yroot,1,nc);
    if(node ->right != NULL) yupdate2(node->yroot,(node->right)->yroot,1,nc);
}

void update(int iP, int iQ, long long K) {
	int P,Q;

	P = iP; Q = iQ;
	P++; Q++;
	findx = P;
	findy = Q;
	value = K;
	xupdate(xroot,1,nr);
}

int sx,ex,sy,ey;
bool crossy(int left,int right){
	if(ey < left || right < sy) return false;
	return true;
}
void ycalc(datay *node,int left,int right){
	if(sy <= left && right <= ey){
		ans = gcd2(ans,node->value);
		return;
	}
	int mid = (left+right)/2;
	if(crossy(left,mid) && node->left != NULL) ycalc(node->left,left,mid);
	if(crossy(mid+1,right) && node->right != NULL) ycalc(node->right,mid+1,right);
}
bool crossx(int left,int right){
	if(ex < left || right < sx) return false;
	return true;
}
void xcalc(datax *node,int left,int right){
	if(sx <= left && right <= ex){
		ycalc(node->yroot,1,nc);

		return;
	}
	int mid = (left+right)/2;
	if(crossx(left,mid) && node -> left != NULL) xcalc(node->left,left,mid);
	if(crossx(mid+1,right) && node -> right != NULL) xcalc(node->right,mid+1,right);
}

long long calculate(int iP, int iQ, int iU, int iV) {
	int P,Q,U,V;

	P = iP; Q = iQ; U = iU; V = iV;
    P++; Q++; U++; V++;
    ans = 0;
    sx = P; ex = U;
    sy = Q; ey = V;
    xcalc(xroot,1,nr);

	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20