oj.uz

Submission #18982

# Submission time Handle Problem Language Result Execution time Memory
18982 2016-02-17T02:00:24 Z suhgyuho_william Game (IOI13_game) C++
63 / 100
 2550 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;
	}
	int 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,int left,int right){
	node -> value = 0;
    if(left == right) return;
    int 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,int left,int right){
	node -> value = gcd2(node->value,node2->value);
	if(left == right) return;
	int 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,int left,int right){
	if(node -> yroot == NULL) node -> yroot = new datay();
	if(left == right){
		yupdate1(node -> yroot,1,nc);
		return;
	}
    int 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) {
	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;
	}
	int 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(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;
	}
	int 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) {
	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 1 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 702 ms 10320 KB Output is correct
5 Correct 409 ms 10320 KB Output is correct
6 Correct 594 ms 10584 KB Output is correct
7 Correct 642 ms 10584 KB Output is correct
8 Correct 424 ms 6492 KB Output is correct
9 Correct 619 ms 10584 KB Output is correct
10 Correct 521 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 1 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 1476 ms 12696 KB Output is correct
13 Correct 2236 ms 6360 KB Output is correct
14 Correct 341 ms 1344 KB Output is correct
15 Correct 2550 ms 9000 KB Output is correct
16 Correct 419 ms 18372 KB Output is correct
17 Correct 968 ms 10980 KB Output is correct
18 Correct 1459 ms 18372 KB Output is correct
19 Correct 1319 ms 18372 KB Output is correct
20 Correct 1102 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 722 ms 10320 KB Output is correct
13 Correct 414 ms 10320 KB Output is correct
14 Correct 565 ms 10584 KB Output is correct
15 Correct 629 ms 10584 KB Output is correct
16 Correct 439 ms 6492 KB Output is correct
17 Correct 625 ms 10584 KB Output is correct
18 Correct 517 ms 10584 KB Output is correct
19 Correct 1485 ms 12696 KB Output is correct
20 Correct 2241 ms 6360 KB Output is correct
21 Correct 307 ms 1344 KB Output is correct
22 Correct 2515 ms 9000 KB Output is correct
23 Correct 400 ms 18372 KB Output is correct
24 Correct 946 ms 10980 KB Output is correct
25 Correct 1511 ms 18372 KB Output is correct
26 Correct 1357 ms 18372 KB Output is correct
27 Correct 1128 ms 18372 KB Output is correct
28 Correct 1086 ms 251880 KB Output is correct
29 Memory limit exceeded 2242 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 1 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 709 ms 10320 KB Output is correct
13 Correct 380 ms 10320 KB Output is correct
14 Correct 611 ms 10584 KB Output is correct
15 Correct 657 ms 10584 KB Output is correct
16 Correct 429 ms 6492 KB Output is correct
17 Correct 630 ms 10584 KB Output is correct
18 Correct 513 ms 10584 KB Output is correct
19 Correct 1480 ms 12696 KB Output is correct
20 Correct 2247 ms 6360 KB Output is correct
21 Correct 327 ms 1344 KB Output is correct
22 Correct 2522 ms 9000 KB Output is correct
23 Correct 413 ms 18372 KB Output is correct
24 Correct 947 ms 10980 KB Output is correct
25 Correct 1552 ms 18372 KB Output is correct
26 Correct 1394 ms 18372 KB Output is correct
27 Correct 1143 ms 18372 KB Output is correct
28 Incorrect 1034 ms 251880 KB Output isn't correct - wrong output format : File not found: "/var/www/temp/18982/outputrrw5_1"
29 Halted 0 ms 0 KB -
30 Halted 0 ms 0 KB -