답안 #18986 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18986	2016-02-17T02:10:17 Z	suhgyuho_william	게임 (IOI13_game)	C++	63 / 100	2520 ms	256000 KB

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;
	}
	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
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	1 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	1 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	0 ms	1212 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	723 ms	10320 KB	Output is correct
5	Correct	444 ms	10320 KB	Output is correct
6	Correct	588 ms	10584 KB	Output is correct
7	Correct	628 ms	10584 KB	Output is correct
8	Correct	432 ms	6492 KB	Output is correct
9	Correct	612 ms	10584 KB	Output is correct
10	Correct	550 ms	10584 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1562 ms	12696 KB	Output is correct
13	Correct	2231 ms	6360 KB	Output is correct
14	Correct	308 ms	1344 KB	Output is correct
15	Correct	2513 ms	9000 KB	Output is correct
16	Correct	414 ms	18372 KB	Output is correct
17	Correct	943 ms	10980 KB	Output is correct
18	Correct	1484 ms	18372 KB	Output is correct
19	Correct	1327 ms	18372 KB	Output is correct
20	Correct	1139 ms	18372 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	1 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	698 ms	10320 KB	Output is correct
13	Correct	423 ms	10320 KB	Output is correct
14	Correct	585 ms	10584 KB	Output is correct
15	Correct	648 ms	10584 KB	Output is correct
16	Correct	470 ms	6492 KB	Output is correct
17	Correct	616 ms	10584 KB	Output is correct
18	Correct	540 ms	10584 KB	Output is correct
19	Correct	1470 ms	12696 KB	Output is correct
20	Correct	2226 ms	6360 KB	Output is correct
21	Correct	276 ms	1344 KB	Output is correct
22	Correct	2518 ms	9000 KB	Output is correct
23	Correct	414 ms	18372 KB	Output is correct
24	Correct	938 ms	10980 KB	Output is correct
25	Correct	1526 ms	18372 KB	Output is correct
26	Correct	1332 ms	18372 KB	Output is correct
27	Correct	1145 ms	18372 KB	Output is correct
28	Correct	1073 ms	251880 KB	Output is correct
29	Memory limit exceeded	2230 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	1 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	1 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	691 ms	10320 KB	Output is correct
13	Correct	447 ms	10320 KB	Output is correct
14	Correct	591 ms	10584 KB	Output is correct
15	Correct	644 ms	10584 KB	Output is correct
16	Correct	441 ms	6492 KB	Output is correct
17	Correct	644 ms	10584 KB	Output is correct
18	Correct	545 ms	10584 KB	Output is correct
19	Correct	1459 ms	12696 KB	Output is correct
20	Correct	2240 ms	6360 KB	Output is correct
21	Correct	302 ms	1344 KB	Output is correct
22	Correct	2520 ms	9000 KB	Output is correct
23	Correct	401 ms	18372 KB	Output is correct
24	Correct	980 ms	10980 KB	Output is correct
25	Correct	1602 ms	18372 KB	Output is correct
26	Correct	1416 ms	18372 KB	Output is correct
27	Correct	1182 ms	18372 KB	Output is correct
28	Incorrect	1019 ms	251880 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/18986/output62i5_1"
29	Halted	0 ms	0 KB	-
30	Halted	0 ms	0 KB	-

답안 #18986

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0