oj.uz

Submission #131099

# Submission time Handle Problem Language Result Execution time Memory
131099 2019-07-16T12:57:58 Z fefe Game (IOI13_game) C++17
63 / 100
 3205 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{
	LL l,r,x;
}root[30*MAX_N],tree[400*MAX_N];
LL n,m;
LL tn,rn;
void init(int R, int C) {
	n=R;
	m=C;
    rn=1;
    tn=0;
}
void updateY(LL x,LL l,LL r,LL q,LL v) {
	if(q < l || q > r)	return ;
	
	
	if(l == r){
		tree[x].x=v;
		return ;
	}
	
	LL mid=(l + r) >> 1;
	
	updateY(tree[x].l ? tree[x].l : (tree[x].l = ++tn),l,mid,q,v);
	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(LL X,LL L,LL R,LL l,LL r,LL 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;
	
	mergeY(tree[X].l ? tree[X].l : (tree[X].l = ++tn),tree[L].l,tree[R].l,l,mid,q);
	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(LL x,LL l,LL r,LL p,LL 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 ;
	}
	
	LL mid=(l+r)>>1;
	
	updateX(root[x].l?root[x].l:(root[x].l=++rn),l,mid,p,q,v);
	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(LL x,LL l,LL r,LL s,LL e) {
	if(!x){
		return 0;
	}
	
	if(r<s || e<l){
		return 0;
	}
	
	if(s <= l && r <= e){
		return tree[x].x;
	}
	
	LL 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(LL x,LL l,LL r,LL sx,LL sy,LL ex,LL ey) {
	
	if(r<sx || ex<l)	return 0;
	
	if(sx <= l && r <= ex){
	
		return readY(root[x].x,0,m-1,sy,ey);
		
	}
	
	LL 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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 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 508 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 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 256 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 376 KB Output is correct
4 Correct 782 ms 15780 KB Output is correct
5 Correct 506 ms 16248 KB Output is correct
6 Correct 781 ms 13168 KB Output is correct
7 Correct 904 ms 12984 KB Output is correct
8 Correct 566 ms 9108 KB Output is correct
9 Correct 916 ms 13116 KB Output is correct
10 Correct 732 ms 12668 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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 476 KB Output is correct
7 Correct 2 ms 504 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 1195 ms 19192 KB Output is correct
13 Correct 2697 ms 7872 KB Output is correct
14 Correct 437 ms 2092 KB Output is correct
15 Correct 3172 ms 11264 KB Output is correct
16 Correct 261 ms 23480 KB Output is correct
17 Correct 1462 ms 15268 KB Output is correct
18 Correct 2401 ms 23844 KB Output is correct
19 Correct 2125 ms 23928 KB Output is correct
20 Correct 1926 ms 23188 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 252 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 774 ms 15712 KB Output is correct
13 Correct 515 ms 16224 KB Output is correct
14 Correct 793 ms 13276 KB Output is correct
15 Correct 896 ms 12908 KB Output is correct
16 Correct 594 ms 9192 KB Output is correct
17 Correct 864 ms 13132 KB Output is correct
18 Correct 734 ms 12620 KB Output is correct
19 Correct 1220 ms 19060 KB Output is correct
20 Correct 2686 ms 7732 KB Output is correct
21 Correct 440 ms 2068 KB Output is correct
22 Correct 3175 ms 11048 KB Output is correct
23 Correct 292 ms 23212 KB Output is correct
24 Correct 1437 ms 15116 KB Output is correct
25 Correct 2569 ms 23728 KB Output is correct
26 Correct 2140 ms 23808 KB Output is correct
27 Correct 2019 ms 23088 KB Output is correct
28 Runtime error 1138 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 372 KB Output is correct
12 Correct 810 ms 15472 KB Output is correct
13 Correct 511 ms 15744 KB Output is correct
14 Correct 787 ms 12748 KB Output is correct
15 Correct 1000 ms 12500 KB Output is correct
16 Correct 586 ms 8696 KB Output is correct
17 Correct 847 ms 12536 KB Output is correct
18 Correct 749 ms 12196 KB Output is correct
19 Correct 1186 ms 18580 KB Output is correct
20 Correct 2712 ms 7436 KB Output is correct
21 Correct 482 ms 1528 KB Output is correct
22 Correct 3205 ms 10620 KB Output is correct
23 Correct 296 ms 23104 KB Output is correct
24 Correct 1679 ms 14792 KB Output is correct
25 Correct 2667 ms 23216 KB Output is correct
26 Correct 2080 ms 23352 KB Output is correct
27 Correct 1936 ms 22820 KB Output is correct
28 Runtime error 1133 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -