Submission #18979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18979	2016-02-17T01:38:14 Z	suhgyuho_william	Game (IOI13_game)	C++	63 / 100	2539 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;

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 && node2->left != NULL) yupdate2(node->left,node2->left,left,mid);
	if(mid+1 <= findy && findy <= right && node2->right != NULL) 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;
    if(left <= findx && findx <= mid){
		if(node -> left == NULL) node -> left = new datax();
        xupdate(node->left,left,mid);
    }
    if(mid+1 <= findx && findx <= right){
		if(node -> right == NULL) node -> right = new datax();
		xupdate(node->right,mid+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) {
	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
10.0 / 10.0

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	671 ms	10320 KB	Output is correct
5	Correct	423 ms	10320 KB	Output is correct
6	Correct	571 ms	10584 KB	Output is correct
7	Correct	622 ms	10584 KB	Output is correct
8	Correct	408 ms	6492 KB	Output is correct
9	Correct	605 ms	10584 KB	Output is correct
10	Correct	522 ms	10584 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	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	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	1462 ms	12696 KB	Output is correct
13	Correct	2243 ms	6360 KB	Output is correct
14	Correct	330 ms	1344 KB	Output is correct
15	Correct	2520 ms	9000 KB	Output is correct
16	Correct	405 ms	18372 KB	Output is correct
17	Correct	900 ms	10980 KB	Output is correct
18	Correct	1446 ms	18372 KB	Output is correct
19	Correct	1282 ms	18372 KB	Output is correct
20	Correct	1051 ms	18372 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
0.0 / 17.0

#	Verdict	Execution time	Memory	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	703 ms	10320 KB	Output is correct
13	Correct	431 ms	10320 KB	Output is correct
14	Correct	578 ms	10584 KB	Output is correct
15	Correct	627 ms	10584 KB	Output is correct
16	Correct	450 ms	6492 KB	Output is correct
17	Correct	614 ms	10584 KB	Output is correct
18	Correct	537 ms	10584 KB	Output is correct
19	Correct	1447 ms	12696 KB	Output is correct
20	Correct	2285 ms	6360 KB	Output is correct
21	Correct	312 ms	1344 KB	Output is correct
22	Correct	2504 ms	9000 KB	Output is correct
23	Correct	458 ms	18372 KB	Output is correct
24	Correct	936 ms	10980 KB	Output is correct
25	Correct	1467 ms	18372 KB	Output is correct
26	Correct	1257 ms	18372 KB	Output is correct
27	Correct	1030 ms	18372 KB	Output is correct
28	Correct	1009 ms	251880 KB	Output is correct
29	Memory limit exceeded	2226 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	Verdict	Execution time	Memory	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	701 ms	10320 KB	Output is correct
13	Correct	444 ms	10320 KB	Output is correct
14	Correct	559 ms	10584 KB	Output is correct
15	Correct	641 ms	10584 KB	Output is correct
16	Correct	426 ms	6492 KB	Output is correct
17	Correct	630 ms	10584 KB	Output is correct
18	Correct	507 ms	10584 KB	Output is correct
19	Correct	1517 ms	12696 KB	Output is correct
20	Correct	2255 ms	6360 KB	Output is correct
21	Correct	314 ms	1344 KB	Output is correct
22	Correct	2539 ms	9000 KB	Output is correct
23	Correct	407 ms	18372 KB	Output is correct
24	Correct	922 ms	10980 KB	Output is correct
25	Correct	1576 ms	18372 KB	Output is correct
26	Correct	1395 ms	18372 KB	Output is correct
27	Correct	1157 ms	18372 KB	Output is correct
28	Incorrect	1073 ms	251880 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/18979/outputWTh5_1"
29	Halted	0 ms	0 KB	-
30	Halted	0 ms	0 KB	-

Submission #18979

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