oj.uz

Submission #18987

# Submission time Handle Problem Language Result Execution time Memory
18987 2016-02-17T02:11:59 Z suhgyuho_william Game (IOI13_game) C++
63 / 100
 2557 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;
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

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

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

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

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