답안 #18987 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18987	2016-02-17T02:11:59 Z	suhgyuho_william	게임 (IOI13_game)	C++	63 / 100	2557 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;
void ycalc(datay *node,int left,int right){
	if(sy <= left && right <= ey){
		ans = gcd2(ans,node->value);
		return;
	}
	if(!((ey < left) || (((left+right)/2) < sy)) && node->left != NULL) ycalc(node->left,left,((left+right)/2));
	if(!((ey < ((left+right)/2)+1) || (right < sy)) && 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	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	672 ms	10320 KB	Output is correct
5	Correct	427 ms	10320 KB	Output is correct
6	Correct	591 ms	10584 KB	Output is correct
7	Correct	668 ms	10584 KB	Output is correct
8	Correct	442 ms	6492 KB	Output is correct
9	Correct	628 ms	10584 KB	Output is correct
10	Correct	530 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	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	1481 ms	12696 KB	Output is correct
13	Correct	2232 ms	6360 KB	Output is correct
14	Correct	301 ms	1344 KB	Output is correct
15	Correct	2534 ms	9000 KB	Output is correct
16	Correct	435 ms	18372 KB	Output is correct
17	Correct	954 ms	10980 KB	Output is correct
18	Correct	1544 ms	18372 KB	Output is correct
19	Correct	1323 ms	18372 KB	Output is correct
20	Correct	1144 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	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	696 ms	10320 KB	Output is correct
13	Correct	397 ms	10320 KB	Output is correct
14	Correct	572 ms	10584 KB	Output is correct
15	Correct	672 ms	10584 KB	Output is correct
16	Correct	465 ms	6492 KB	Output is correct
17	Correct	625 ms	10584 KB	Output is correct
18	Correct	515 ms	10584 KB	Output is correct
19	Correct	1522 ms	12696 KB	Output is correct
20	Correct	2253 ms	6360 KB	Output is correct
21	Correct	338 ms	1344 KB	Output is correct
22	Correct	2532 ms	9000 KB	Output is correct
23	Correct	436 ms	18372 KB	Output is correct
24	Correct	950 ms	10980 KB	Output is correct
25	Correct	1537 ms	18372 KB	Output is correct
26	Correct	1351 ms	18372 KB	Output is correct
27	Correct	1162 ms	18372 KB	Output is correct
28	Correct	1068 ms	251880 KB	Output is correct
29	Memory limit exceeded	2275 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	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	695 ms	10320 KB	Output is correct
13	Correct	406 ms	10320 KB	Output is correct
14	Correct	606 ms	10584 KB	Output is correct
15	Correct	663 ms	10584 KB	Output is correct
16	Correct	409 ms	6492 KB	Output is correct
17	Correct	657 ms	10584 KB	Output is correct
18	Correct	567 ms	10584 KB	Output is correct
19	Correct	1516 ms	12696 KB	Output is correct
20	Correct	2262 ms	6360 KB	Output is correct
21	Correct	325 ms	1344 KB	Output is correct
22	Correct	2557 ms	9000 KB	Output is correct
23	Correct	429 ms	18372 KB	Output is correct
24	Correct	988 ms	10980 KB	Output is correct
25	Correct	1571 ms	18372 KB	Output is correct
26	Correct	1442 ms	18372 KB	Output is correct
27	Correct	1178 ms	18372 KB	Output is correct
28	Correct	1081 ms	251880 KB	Output is correct
29	Memory limit exceeded	2263 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

답안 #18987

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