oj.uz

Submission #131085

# Submission time Handle Problem Language Result Execution time Memory
131085 2019-07-16T12:50:50 Z fefe Game (IOI13_game) C++17
63 / 100
 3206 ms 109344 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[16*MAX_N],tree[100*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 256 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 2 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 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 376 KB Output is correct
4 Correct 813 ms 18560 KB Output is correct
5 Correct 506 ms 19248 KB Output is correct
6 Correct 787 ms 16912 KB Output is correct
7 Correct 892 ms 16568 KB Output is correct
8 Correct 555 ms 12320 KB Output is correct
9 Correct 821 ms 16760 KB Output is correct
10 Correct 716 ms 16356 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 504 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 256 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 1210 ms 21808 KB Output is correct
13 Correct 2693 ms 10900 KB Output is correct
14 Correct 439 ms 5752 KB Output is correct
15 Correct 3191 ms 14528 KB Output is correct
16 Correct 274 ms 26752 KB Output is correct
17 Correct 1490 ms 18980 KB Output is correct
18 Correct 2513 ms 27976 KB Output is correct
19 Correct 2174 ms 28244 KB Output is correct
20 Correct 1912 ms 27664 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 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 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 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 780 ms 18392 KB Output is correct
13 Correct 503 ms 19148 KB Output is correct
14 Correct 775 ms 16996 KB Output is correct
15 Correct 895 ms 16572 KB Output is correct
16 Correct 554 ms 12412 KB Output is correct
17 Correct 836 ms 16820 KB Output is correct
18 Correct 737 ms 16392 KB Output is correct
19 Correct 1205 ms 22264 KB Output is correct
20 Correct 2716 ms 11028 KB Output is correct
21 Correct 438 ms 5880 KB Output is correct
22 Correct 3206 ms 14548 KB Output is correct
23 Correct 268 ms 26644 KB Output is correct
24 Correct 1457 ms 19000 KB Output is correct
25 Correct 2485 ms 28048 KB Output is correct
26 Correct 2235 ms 28244 KB Output is correct
27 Correct 2028 ms 27612 KB Output is correct
28 Runtime error 251 ms 109172 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 256 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 256 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 3 ms 476 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 368 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 795 ms 18404 KB Output is correct
13 Correct 507 ms 19108 KB Output is correct
14 Correct 811 ms 16796 KB Output is correct
15 Correct 927 ms 16608 KB Output is correct
16 Correct 556 ms 12408 KB Output is correct
17 Correct 851 ms 16692 KB Output is correct
18 Correct 805 ms 16524 KB Output is correct
19 Correct 1250 ms 22264 KB Output is correct
20 Correct 2691 ms 10756 KB Output is correct
21 Correct 437 ms 5672 KB Output is correct
22 Correct 3195 ms 14444 KB Output is correct
23 Correct 269 ms 26612 KB Output is correct
24 Correct 1512 ms 19012 KB Output is correct
25 Correct 2569 ms 28140 KB Output is correct
26 Correct 2173 ms 28540 KB Output is correct
27 Correct 1904 ms 27764 KB Output is correct
28 Runtime error 249 ms 109344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -