oj.uz

답안 #18985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18985 2016-02-17T02:09:27 Z suhgyuho_william 게임 (IOI13_game) C++
0 / 100
 0 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;

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

void xcalc(datax *node,int left,int right){
	if(sx <= left && right <= ex){
		ycalc(node->yroot,1,nc);

		return;
	}
	if(!((ex < left || ((left+right)/2)) < sx) && node -> left != NULL) xcalc(node->left,left,((left+right)/2));
	if(!(ex < ((left+right)/2)+1 || right < sx) && node -> right != NULL) xcalc(node->right,((left+right)/2)+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
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 Correct 0 ms 1212 KB Output is correct
3 Incorrect 0 ms 1212 KB Output isn't correct
4 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 0 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 -