oj.uz

Submission #131096

# Submission time Handle Problem Language Result Execution time Memory
131096 2019-07-16T12:56:07 Z fefe Game (IOI13_game) C++17
63 / 100
 3252 ms 216656 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[200*MAX_N],tree[200*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 380 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 3 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 3 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 778 ms 15284 KB Output is correct
5 Correct 516 ms 15440 KB Output is correct
6 Correct 779 ms 12472 KB Output is correct
7 Correct 895 ms 12100 KB Output is correct
8 Correct 563 ms 8432 KB Output is correct
9 Correct 871 ms 12244 KB Output is correct
10 Correct 770 ms 11892 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 376 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 360 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 1195 ms 18292 KB Output is correct
13 Correct 2711 ms 7180 KB Output is correct
14 Correct 475 ms 1364 KB Output is correct
15 Correct 3158 ms 10364 KB Output is correct
16 Correct 268 ms 22812 KB Output is correct
17 Correct 1495 ms 14456 KB Output is correct
18 Correct 2541 ms 22996 KB Output is correct
19 Correct 2296 ms 23364 KB Output is correct
20 Correct 1968 ms 22848 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 256 KB Output is correct
2 Correct 3 ms 508 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 3 ms 500 KB Output is correct
7 Correct 2 ms 252 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 801 ms 15376 KB Output is correct
13 Correct 507 ms 15604 KB Output is correct
14 Correct 859 ms 12720 KB Output is correct
15 Correct 915 ms 12424 KB Output is correct
16 Correct 583 ms 8656 KB Output is correct
17 Correct 872 ms 12484 KB Output is correct
18 Correct 753 ms 12076 KB Output is correct
19 Correct 1231 ms 18544 KB Output is correct
20 Correct 2712 ms 7380 KB Output is correct
21 Correct 434 ms 1468 KB Output is correct
22 Correct 3252 ms 10684 KB Output is correct
23 Correct 273 ms 22736 KB Output is correct
24 Correct 1486 ms 14544 KB Output is correct
25 Correct 2581 ms 23184 KB Output is correct
26 Correct 2154 ms 23328 KB Output is correct
27 Correct 2033 ms 22648 KB Output is correct
28 Runtime error 533 ms 216172 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 376 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 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 806 ms 15692 KB Output is correct
13 Correct 504 ms 15924 KB Output is correct
14 Correct 776 ms 13000 KB Output is correct
15 Correct 898 ms 12628 KB Output is correct
16 Correct 558 ms 8952 KB Output is correct
17 Correct 866 ms 12792 KB Output is correct
18 Correct 746 ms 12408 KB Output is correct
19 Correct 1193 ms 18832 KB Output is correct
20 Correct 2720 ms 7624 KB Output is correct
21 Correct 435 ms 1772 KB Output is correct
22 Correct 3249 ms 10924 KB Output is correct
23 Correct 307 ms 23276 KB Output is correct
24 Correct 1503 ms 14984 KB Output is correct
25 Correct 2469 ms 23580 KB Output is correct
26 Correct 2142 ms 23684 KB Output is correct
27 Correct 2047 ms 23108 KB Output is correct
28 Runtime error 533 ms 216656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -