답안 #18983 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18983	2016-02-17T02:04:05 Z	suhgyuho_william	게임 (IOI13_game)	C++	63 / 100	2541 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);
}
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;
	}
	if(crossx(left,((left+right)/2)) && node -> left != NULL) xcalc(node->left,left,((left+right)/2));
	if(crossx(((left+right)/2)+1,right) && 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	1212 KB	Output is correct
2	Correct	1212 KB	Output is correct
3	Correct	1212 KB	Output is correct
4	Correct	1212 KB	Output is correct
5	Correct	1212 KB	Output is correct
6	Correct	1212 KB	Output is correct
7	Correct	1212 KB	Output is correct
8	Correct	1212 KB	Output is correct
9	Correct	1212 KB	Output is correct
10	Correct	1212 KB	Output is correct
11	Correct	1212 KB	Output is correct
12	Correct	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	703 ms	10320 KB	Output is correct
5	Correct	422 ms	10320 KB	Output is correct
6	Correct	573 ms	10584 KB	Output is correct
7	Correct	646 ms	10584 KB	Output is correct
8	Correct	448 ms	6492 KB	Output is correct
9	Correct	633 ms	10584 KB	Output is correct
10	Correct	526 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	1493 ms	12696 KB	Output is correct
13	Correct	2229 ms	6360 KB	Output is correct
14	Correct	326 ms	1344 KB	Output is correct
15	Correct	2526 ms	9000 KB	Output is correct
16	Correct	406 ms	18372 KB	Output is correct
17	Correct	965 ms	10980 KB	Output is correct
18	Correct	1492 ms	18372 KB	Output is correct
19	Correct	1347 ms	18372 KB	Output is correct
20	Correct	1110 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	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	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	693 ms	10320 KB	Output is correct
13	Correct	444 ms	10320 KB	Output is correct
14	Correct	587 ms	10584 KB	Output is correct
15	Correct	671 ms	10584 KB	Output is correct
16	Correct	439 ms	6492 KB	Output is correct
17	Correct	624 ms	10584 KB	Output is correct
18	Correct	515 ms	10584 KB	Output is correct
19	Correct	1497 ms	12696 KB	Output is correct
20	Correct	2255 ms	6360 KB	Output is correct
21	Correct	328 ms	1344 KB	Output is correct
22	Correct	2518 ms	9000 KB	Output is correct
23	Correct	417 ms	18372 KB	Output is correct
24	Correct	960 ms	10980 KB	Output is correct
25	Correct	1543 ms	18372 KB	Output is correct
26	Correct	1355 ms	18372 KB	Output is correct
27	Correct	1138 ms	18372 KB	Output is correct
28	Correct	1022 ms	251880 KB	Output is correct
29	Memory limit exceeded	2264 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	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	1 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	683 ms	10320 KB	Output is correct
13	Correct	421 ms	10320 KB	Output is correct
14	Correct	592 ms	10584 KB	Output is correct
15	Correct	674 ms	10584 KB	Output is correct
16	Correct	443 ms	6492 KB	Output is correct
17	Correct	651 ms	10584 KB	Output is correct
18	Correct	530 ms	10584 KB	Output is correct
19	Correct	1481 ms	12696 KB	Output is correct
20	Correct	2246 ms	6360 KB	Output is correct
21	Correct	313 ms	1344 KB	Output is correct
22	Correct	2541 ms	9000 KB	Output is correct
23	Correct	407 ms	18372 KB	Output is correct
24	Correct	954 ms	10980 KB	Output is correct
25	Correct	1570 ms	18372 KB	Output is correct
26	Correct	1412 ms	18372 KB	Output is correct
27	Correct	1183 ms	18372 KB	Output is correct
28	Incorrect	1109 ms	251880 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/18983/outputxCj5_1"
29	Halted	0 ms	0 KB	-
30	Halted	0 ms	0 KB	-

답안 #18983

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