oj.uz

Submission #131103

# Submission time Handle Problem Language Result Execution time Memory
131103 2019-07-16T13:09:03 Z fefe Game (IOI13_game) C++17
63 / 100
 3124 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[31*MAX_N],tree[900*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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 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 3 ms 380 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 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 760 ms 11468 KB Output is correct
5 Correct 525 ms 11896 KB Output is correct
6 Correct 731 ms 8632 KB Output is correct
7 Correct 827 ms 8544 KB Output is correct
8 Correct 536 ms 6216 KB Output is correct
9 Correct 803 ms 8724 KB Output is correct
10 Correct 714 ms 8252 KB Output is correct
11 Correct 3 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 368 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 380 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 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 1173 ms 13688 KB Output is correct
13 Correct 2666 ms 5248 KB Output is correct
14 Correct 436 ms 1144 KB Output is correct
15 Correct 3124 ms 7376 KB Output is correct
16 Correct 250 ms 15624 KB Output is correct
17 Correct 1454 ms 10204 KB Output is correct
18 Correct 2201 ms 15900 KB Output is correct
19 Correct 1961 ms 16148 KB Output is correct
20 Correct 1729 ms 15536 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 3 ms 376 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 376 KB Output is correct
12 Correct 766 ms 11796 KB Output is correct
13 Correct 497 ms 11888 KB Output is correct
14 Correct 740 ms 8852 KB Output is correct
15 Correct 834 ms 8544 KB Output is correct
16 Correct 541 ms 6392 KB Output is correct
17 Correct 819 ms 8824 KB Output is correct
18 Correct 708 ms 8384 KB Output is correct
19 Correct 1173 ms 13764 KB Output is correct
20 Correct 2654 ms 5208 KB Output is correct
21 Correct 439 ms 1272 KB Output is correct
22 Correct 3111 ms 7508 KB Output is correct
23 Correct 247 ms 15476 KB Output is correct
24 Correct 1384 ms 10304 KB Output is correct
25 Correct 2212 ms 15888 KB Output is correct
26 Correct 2020 ms 15956 KB Output is correct
27 Correct 1790 ms 15440 KB Output is correct
28 Correct 1486 ms 253124 KB Output is correct
29 Runtime error 2640 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 376 KB Output is correct
2 Correct 3 ms 504 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 376 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 757 ms 11396 KB Output is correct
13 Correct 499 ms 11676 KB Output is correct
14 Correct 750 ms 8616 KB Output is correct
15 Correct 852 ms 8260 KB Output is correct
16 Correct 542 ms 6192 KB Output is correct
17 Correct 834 ms 8696 KB Output is correct
18 Correct 706 ms 8152 KB Output is correct
19 Correct 1181 ms 13640 KB Output is correct
20 Correct 2644 ms 5096 KB Output is correct
21 Correct 434 ms 1016 KB Output is correct
22 Correct 3107 ms 7256 KB Output is correct
23 Correct 249 ms 15408 KB Output is correct
24 Correct 1610 ms 10104 KB Output is correct
25 Correct 2235 ms 15784 KB Output is correct
26 Correct 1900 ms 15944 KB Output is correct
27 Correct 2176 ms 15216 KB Output is correct
28 Correct 1505 ms 252340 KB Output is correct
29 Runtime error 2690 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -