oj.uz

답안 #18978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18978 2016-02-17T01:35:28 Z suhgyuho_william 게임 (IOI13_game) C++
0 / 100
 1 ms 1212 KB 
#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;

lld R,C;
long long nr,nc;

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

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

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

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

lld sx,ex,sy,ey;
bool crossy(lld left,lld right){
	if(ey < left || right < sy) return false;
	return true;
}
void ycalc(datay *node,lld left,lld right){
	if(sy <= left && right <= ey){
		ans = gcd2(ans,node->value);
		return;
	}
	lld 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(lld left,lld right){
	if(ex < left || right < sx) return false;
	return true;
}
void xcalc(datax *node,lld left,lld right){
	if(sx <= left && right <= ex){
		ycalc(node->yroot,1,nc);

		return;
	}
	lld 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) {
	lld i,j;
	lld P,Q,U,V;

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

	return ans;
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 0 ms 1212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 0 ms 1212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 0 ms 1212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 1 ms 1212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Incorrect 0 ms 1212 KB Output isn't correct
3 Halted 0 ms 0 KB -