oj.uz

Submission #131110

# Submission time Handle Problem Language Result Execution time Memory
131110 2019-07-16T13:25:32 Z fefe Game (IOI13_game) C++17
80 / 100
 8265 ms 256000 KB 
#include "game.h"

#include<bits/stdc++.h>
#define MAX_N 22005
typedef long long LL;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Tree{
	int l,r;
	LL x;
}root[33*MAX_N],tree[450*MAX_N];
int n,m;
int tn,rn;
void init(int R, int C) {
	n=R;
	m=C;
    rn=1;
    tn=0;
}
void updateY(int x,int l,int r,int q,LL v) {
	if(q < l || q > r)	return ;
	
	
	if(l == r){
		tree[x].x=v;
		return ;
	}
	
	LL mid=(l + r) >> 1;
	
	if(q<=mid)	updateY(tree[x].l ? tree[x].l : (tree[x].l = ++tn),l,mid,q,v);
	if(q>mid)	updateY(tree[x].r ? tree[x].r : (tree[x].r = ++tn),mid+1,r,q,v);
	
	tree[x].x=gcd2(tree[tree[x].l].x,tree[tree[x].r].x);
	
}

void mergeY(int X,int L,int R,int l,int r,int q){
	
	if(q < l || q > r)	return ;

	if(L==0 && R==0){
		return ;
	}
	
	if(l == r){
		tree[X].x=gcd2(tree[L].x,tree[R].x);
		return ;
	}
	
	int mid=(l + r) >> 1;
	
	if(q<=mid)	mergeY(tree[X].l ? tree[X].l : (tree[X].l = ++tn),tree[L].l,tree[R].l,l,mid,q);
	if(q>mid)	mergeY(tree[X].r ? tree[X].r : (tree[X].r = ++tn),tree[L].r,tree[R].r,mid+1,r,q);
	
	tree[X].x=gcd2(tree[L].x,tree[R].x);
}

void updateX(int x,int l,int r,int p,int q,LL v) {
	if(p<l || p>r)	return ;
	
	if(l==r){
		updateY(root[x].x?root[x].x:(root[x].x=++tn),0,m-1,q,v);
		return ;
	}
	
	int mid=(l+r)>>1;
	
	if(p<=mid)	updateX(root[x].l?root[x].l:(root[x].l=++rn),l,mid,p,q,v);
	if(p>mid)	updateX(root[x].r?root[x].r:(root[x].r=++rn),mid+1,r,p,q,v);
	
	
	mergeY(root[x].x?root[x].x:(root[x].x=++tn),root[root[x].l].x,root[root[x].r].x,0,m-1,q);
}

void update(int P, int Q, long long K) {
    updateX(1,0,n-1,P,Q,K);
}
LL readY(int x,int l,int r,int s,int e) {
	if(!x){
		return 0;
	}
	
	if(r<s || e<l){
		return 0;
	}
	
	if(s <= l && r <= e){
		return tree[x].x;
	}
	
	int mid = (l + r) >> 1;
	
	return gcd2(readY(tree[x].l,l,mid,s,e),readY(tree[x].r,mid+1,r,s,e));
	
}

LL readX(int x,int l,int r,int sx,int sy,int ex,int ey) {
	
	if(r<sx || ex<l)	return 0;
	
	if(sx <= l && r <= ex){
	
		return readY(root[x].x,0,m-1,sy,ey);
		
	}
	
	int mid = (l + r) >> 1;
	
	return gcd2(readX(root[x].l,l,mid,sx,sy,ex,ey),readX(root[x].r,mid+1,r,sx,sy,ex,ey));
	
}


long long calculate(int P, int Q, int U, int V) {
	
	return readX(1,0,n-1,P,Q,U,V);
	
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 728 ms 8684 KB Output is correct
5 Correct 482 ms 8948 KB Output is correct
6 Correct 696 ms 5752 KB Output is correct
7 Correct 778 ms 5548 KB Output is correct
8 Correct 511 ms 4476 KB Output is correct
9 Correct 762 ms 5752 KB Output is correct
10 Correct 637 ms 5212 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1132 ms 10204 KB Output is correct
13 Correct 2671 ms 3864 KB Output is correct
14 Correct 409 ms 1016 KB Output is correct
15 Correct 3148 ms 5152 KB Output is correct
16 Correct 236 ms 9720 KB Output is correct
17 Correct 1223 ms 6628 KB Output is correct
18 Correct 2016 ms 10200 KB Output is correct
19 Correct 1768 ms 10232 KB Output is correct
20 Correct 1593 ms 9720 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 734 ms 8552 KB Output is correct
13 Correct 471 ms 8984 KB Output is correct
14 Correct 712 ms 5752 KB Output is correct
15 Correct 793 ms 5480 KB Output is correct
16 Correct 518 ms 4472 KB Output is correct
17 Correct 754 ms 5752 KB Output is correct
18 Correct 637 ms 5072 KB Output is correct
19 Correct 1137 ms 10200 KB Output is correct
20 Correct 2697 ms 3696 KB Output is correct
21 Correct 409 ms 1016 KB Output is correct
22 Correct 3151 ms 5148 KB Output is correct
23 Correct 235 ms 9732 KB Output is correct
24 Correct 1243 ms 6788 KB Output is correct
25 Correct 1952 ms 10104 KB Output is correct
26 Correct 1710 ms 10492 KB Output is correct
27 Correct 1545 ms 9780 KB Output is correct
28 Correct 1151 ms 126456 KB Output is correct
29 Correct 2384 ms 151648 KB Output is correct
30 Correct 8242 ms 109392 KB Output is correct
31 Correct 7864 ms 85324 KB Output is correct
32 Correct 892 ms 10488 KB Output is correct
33 Correct 1055 ms 11524 KB Output is correct
34 Correct 588 ms 145368 KB Output is correct
35 Correct 1932 ms 80448 KB Output is correct
36 Correct 3473 ms 149736 KB Output is correct
37 Correct 2832 ms 149592 KB Output is correct
38 Correct 2797 ms 149144 KB Output is correct
39 Correct 2506 ms 117224 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 733 ms 8756 KB Output is correct
13 Correct 469 ms 9080 KB Output is correct
14 Correct 698 ms 6112 KB Output is correct
15 Correct 778 ms 5752 KB Output is correct
16 Correct 512 ms 4600 KB Output is correct
17 Correct 741 ms 5932 KB Output is correct
18 Correct 639 ms 5396 KB Output is correct
19 Correct 1134 ms 10564 KB Output is correct
20 Correct 2671 ms 4024 KB Output is correct
21 Correct 408 ms 1276 KB Output is correct
22 Correct 3130 ms 5288 KB Output is correct
23 Correct 231 ms 10104 KB Output is correct
24 Correct 1202 ms 6956 KB Output is correct
25 Correct 1977 ms 10376 KB Output is correct
26 Correct 1713 ms 10644 KB Output is correct
27 Correct 1607 ms 9940 KB Output is correct
28 Correct 1147 ms 126700 KB Output is correct
29 Correct 2332 ms 151572 KB Output is correct
30 Correct 8265 ms 109288 KB Output is correct
31 Correct 7816 ms 85368 KB Output is correct
32 Correct 903 ms 10536 KB Output is correct
33 Correct 1052 ms 11768 KB Output is correct
34 Correct 583 ms 145272 KB Output is correct
35 Correct 1906 ms 80612 KB Output is correct
36 Correct 3327 ms 149576 KB Output is correct
37 Correct 2828 ms 149644 KB Output is correct
38 Correct 2729 ms 149104 KB Output is correct
39 Runtime error 1069 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -