oj.uz

Submission #18686

# Submission time Handle Problem Language Result Execution time Memory
18686 2016-02-14T03:26:37 Z suhgyuho_william Game (IOI13_game) C++
36 / 100
 1955 ms 204300 KB 
#include "game.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 data{
	long long s,e;
	data *par,*left,*right;
	data(){}
	data(data *ipar,long long is,long long ie){
		s = is; e = ie;
		par = ipar;
		left = right = NULL;
	}
};

long long nr,nc;
long long seg[5100][5100];

void init(int iR, int iC) {
	lld R,C;
	R = (lld)iR; C = (lld)iC;
	if(R > 2000 || C > 2000) exit(0);
    for(nr = 1; nr < R; nr *= 2);
    for(nc = 1; nc < C; nc *= 2);
}

void update(int iP, int iQ, long long K) {
	lld i,j;
	lld P,Q;

	P = (lld)iP; Q = (lld)iQ;
	P++; Q++;
	i = nr+P-1;
	j = nc+Q-1; seg[i][j] = K; j /= 2;
	while(j > 0){
		seg[i][j] = gcd2(seg[i][j*2],seg[i][(j*2)+1]);
		j /= 2;
	}
	i /= 2;
	while(i > 0){
		j = nc+Q-1;
		while(j > 0){
			seg[i][j] = gcd2(seg[i*2][j],seg[(i*2)+1][j]);
			j /= 2;
		}
		i /= 2;
	}
}

lld cnt1,cnt2;
lld p1[1000],p2[1000];
lld sr,er,sc,ec;
void find1(lld node,lld left,lld right){
	if(er < left || right < sr) return;
	if(sr <= left && right <= er){
		cnt1++;
		p1[cnt1] = node;
		return;
	}
	lld mid = (left+right)/2;
	find1(node*2,left,mid);
	find1((node*2)+1,mid+1,right);
}
void find2(lld node,lld left,lld right){
	if(ec < left || right < sc) return;
	if(sc <= left && right <= ec){
		cnt2++;
		p2[cnt2] = node;
		return;
	}
	lld mid = (left+right)/2;
	find2(node*2,left,mid);
	find2((node*2)+1,mid+1,right);
}

long long calculate(int iP, int iQ, int iU, int iV) {
	lld i,j;
	lld ans = 0;
	lld P,Q,U,V;

	P = (lld)iP; Q = (lld)iQ; U = (lld)iU; V = (lld)iV;
    P++; Q++; U++; V++;
	sr = P; er = U;
	sc = Q; ec = V;
	cnt1 = 0; find1(1,1,nr);
	cnt2 = 0; find2(1,1,nc);
	for(i=1; i<=cnt1; i++){
		for(j=1; j<=cnt2; j++){
			ans = gcd2(ans,seg[p1[i]][p2[j]]);
		}
	}

	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204300 KB Output is correct
2 Correct 2 ms 204300 KB Output is correct
3 Correct 0 ms 204300 KB Output is correct
4 Correct 0 ms 204300 KB Output is correct
5 Correct 0 ms 204300 KB Output is correct
6 Correct 0 ms 204300 KB Output is correct
7 Correct 0 ms 204300 KB Output is correct
8 Correct 0 ms 204300 KB Output is correct
9 Correct 2 ms 204300 KB Output is correct
10 Correct 0 ms 204300 KB Output is correct
11 Correct 0 ms 204300 KB Output is correct
12 Correct 0 ms 204300 KB Output is correct

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204300 KB Output is correct
2 Correct 0 ms 204300 KB Output is correct
3 Correct 0 ms 204300 KB Output is correct
4 Incorrect 0 ms 204296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204300 KB Output is correct
2 Correct 0 ms 204300 KB Output is correct
3 Correct 0 ms 204300 KB Output is correct
4 Correct 0 ms 204300 KB Output is correct
5 Correct 0 ms 204300 KB Output is correct
6 Correct 0 ms 204300 KB Output is correct
7 Correct 0 ms 204300 KB Output is correct
8 Correct 0 ms 204300 KB Output is correct
9 Correct 0 ms 204300 KB Output is correct
10 Correct 0 ms 204300 KB Output is correct
11 Correct 0 ms 204300 KB Output is correct
12 Correct 1108 ms 204300 KB Output is correct
13 Correct 1759 ms 204300 KB Output is correct
14 Correct 403 ms 204300 KB Output is correct
15 Correct 1955 ms 204300 KB Output is correct
16 Correct 289 ms 204300 KB Output is correct
17 Correct 770 ms 204300 KB Output is correct
18 Correct 1017 ms 204300 KB Output is correct
19 Correct 928 ms 204300 KB Output is correct
20 Correct 754 ms 204300 KB Output is correct
21 Correct 0 ms 204300 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204300 KB Output is correct
2 Correct 0 ms 204300 KB Output is correct
3 Correct 0 ms 204300 KB Output is correct
4 Correct 0 ms 204300 KB Output is correct
5 Correct 0 ms 204300 KB Output is correct
6 Correct 0 ms 204300 KB Output is correct
7 Correct 0 ms 204300 KB Output is correct
8 Correct 0 ms 204300 KB Output is correct
9 Correct 0 ms 204300 KB Output is correct
10 Correct 0 ms 204300 KB Output is correct
11 Correct 0 ms 204300 KB Output is correct
12 Incorrect 0 ms 204296 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204300 KB Output is correct
2 Correct 0 ms 204300 KB Output is correct
3 Correct 0 ms 204300 KB Output is correct
4 Correct 0 ms 204300 KB Output is correct
5 Correct 0 ms 204300 KB Output is correct
6 Correct 0 ms 204300 KB Output is correct
7 Correct 0 ms 204300 KB Output is correct
8 Correct 0 ms 204300 KB Output is correct
9 Correct 0 ms 204300 KB Output is correct
10 Correct 0 ms 204300 KB Output is correct
11 Correct 0 ms 204300 KB Output is correct
12 Incorrect 0 ms 204296 KB Output isn't correct
13 Halted 0 ms 0 KB -