oj.uz

Submission #131104

# Submission time Handle Problem Language Result Execution time Memory
131104 2019-07-16T13:11:18 Z fefe Game (IOI13_game) C++17
63 / 100
 3134 ms 256004 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[975*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;
	
	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(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;
	
	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(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;
	
	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(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 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 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.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 781 ms 11460 KB Output is correct
5 Correct 500 ms 11660 KB Output is correct
6 Correct 728 ms 8700 KB Output is correct
7 Correct 839 ms 8484 KB Output is correct
8 Correct 532 ms 6008 KB Output is correct
9 Correct 815 ms 8596 KB Output is correct
10 Correct 734 ms 8144 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 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 252 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 380 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1201 ms 13532 KB Output is correct
13 Correct 2673 ms 5000 KB Output is correct
14 Correct 442 ms 976 KB Output is correct
15 Correct 3134 ms 7244 KB Output is correct
16 Correct 251 ms 15396 KB Output is correct
17 Correct 1345 ms 10160 KB Output is correct
18 Correct 2291 ms 15940 KB Output is correct
19 Correct 2103 ms 15852 KB Output is correct
20 Correct 1790 ms 15316 KB Output is correct
21 Correct 2 ms 256 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 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 3 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 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 757 ms 11320 KB Output is correct
13 Correct 499 ms 11684 KB Output is correct
14 Correct 739 ms 8736 KB Output is correct
15 Correct 815 ms 8452 KB Output is correct
16 Correct 546 ms 6268 KB Output is correct
17 Correct 854 ms 8488 KB Output is correct
18 Correct 691 ms 8056 KB Output is correct
19 Correct 1241 ms 13708 KB Output is correct
20 Correct 2654 ms 5032 KB Output is correct
21 Correct 434 ms 1088 KB Output is correct
22 Correct 3129 ms 7064 KB Output is correct
23 Correct 252 ms 15328 KB Output is correct
24 Correct 1326 ms 10104 KB Output is correct
25 Correct 2242 ms 15764 KB Output is correct
26 Correct 1915 ms 15864 KB Output is correct
27 Correct 1765 ms 15224 KB Output is correct
28 Correct 1488 ms 244456 KB Output is correct
29 Runtime error 2658 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 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 380 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 376 KB Output is correct
6 Correct 2 ms 376 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 753 ms 11672 KB Output is correct
13 Correct 495 ms 11644 KB Output is correct
14 Correct 723 ms 8584 KB Output is correct
15 Correct 829 ms 8464 KB Output is correct
16 Correct 535 ms 6156 KB Output is correct
17 Correct 787 ms 8572 KB Output is correct
18 Correct 679 ms 8108 KB Output is correct
19 Correct 1181 ms 13572 KB Output is correct
20 Correct 2657 ms 5104 KB Output is correct
21 Correct 445 ms 1016 KB Output is correct
22 Correct 3124 ms 7216 KB Output is correct
23 Correct 248 ms 15352 KB Output is correct
24 Correct 1353 ms 10084 KB Output is correct
25 Correct 2517 ms 15932 KB Output is correct
26 Correct 1907 ms 15860 KB Output is correct
27 Correct 1808 ms 15420 KB Output is correct
28 Correct 1462 ms 244556 KB Output is correct
29 Runtime error 2648 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -