oj.uz

Submission #18983

# Submission time Handle Problem Language Result Execution time Memory
18983 2016-02-17T02:04:05 Z suhgyuho_william Game (IOI13_game) C++
63 / 100
 2541 ms 256000 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);
}
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

# 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 0 ms 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 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

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

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

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