oj.uz

Submission #131102

# Submission time Handle Problem Language Result Execution time Memory
131102 2019-07-16T13:03:07 Z fefe Game (IOI13_game) C++17
63 / 100
 3124 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{
	int l,r;
	LL x;
}root[100*MAX_N],tree[400*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 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 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 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 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 756 ms 11740 KB Output is correct
5 Correct 499 ms 12120 KB Output is correct
6 Correct 737 ms 9136 KB Output is correct
7 Correct 835 ms 8560 KB Output is correct
8 Correct 536 ms 6300 KB Output is correct
9 Correct 807 ms 8824 KB Output is correct
10 Correct 702 ms 8312 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 376 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 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 1179 ms 13952 KB Output is correct
13 Correct 2689 ms 5240 KB Output is correct
14 Correct 445 ms 1272 KB Output is correct
15 Correct 3124 ms 7416 KB Output is correct
16 Correct 250 ms 15608 KB Output is correct
17 Correct 1334 ms 10344 KB Output is correct
18 Correct 2198 ms 16008 KB Output is correct
19 Correct 1944 ms 16316 KB Output is correct
20 Correct 1833 ms 15428 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 376 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 1 ms 376 KB Output is correct
10 Correct 2 ms 312 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 754 ms 11640 KB Output is correct
13 Correct 508 ms 12024 KB Output is correct
14 Correct 748 ms 9088 KB Output is correct
15 Correct 857 ms 8696 KB Output is correct
16 Correct 547 ms 6264 KB Output is correct
17 Correct 812 ms 8824 KB Output is correct
18 Correct 756 ms 8456 KB Output is correct
19 Correct 1189 ms 13916 KB Output is correct
20 Correct 2662 ms 5248 KB Output is correct
21 Correct 436 ms 1272 KB Output is correct
22 Correct 3105 ms 7376 KB Output is correct
23 Correct 253 ms 15608 KB Output is correct
24 Correct 1343 ms 10288 KB Output is correct
25 Correct 2193 ms 15992 KB Output is correct
26 Correct 1940 ms 16248 KB Output is correct
27 Correct 1747 ms 15536 KB Output is correct
28 Runtime error 946 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 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 380 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 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 752 ms 11360 KB Output is correct
13 Correct 499 ms 11656 KB Output is correct
14 Correct 753 ms 8552 KB Output is correct
15 Correct 827 ms 8248 KB Output is correct
16 Correct 539 ms 6136 KB Output is correct
17 Correct 801 ms 8468 KB Output is correct
18 Correct 686 ms 8148 KB Output is correct
19 Correct 1174 ms 13560 KB Output is correct
20 Correct 2652 ms 4928 KB Output is correct
21 Correct 436 ms 920 KB Output is correct
22 Correct 3093 ms 7244 KB Output is correct
23 Correct 249 ms 15352 KB Output is correct
24 Correct 1351 ms 10192 KB Output is correct
25 Correct 2236 ms 15736 KB Output is correct
26 Correct 1883 ms 15980 KB Output is correct
27 Correct 1706 ms 15304 KB Output is correct
28 Runtime error 920 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -