oj.uz

Submission #18685

# Submission time Handle Problem Language Result Execution time Memory
18685 2016-02-14T03:24:56 Z suhgyuho_william Game (IOI13_game) C++
10 / 100
 1756 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;
		seg[i][j] = K;
		j /= 2;
		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 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 2 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 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
0.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 1 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 1115 ms 204300 KB Output is correct
13 Incorrect 1756 ms 204300 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.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 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 -