oj.uz

Submission #131093

# Submission time Handle Problem Language Result Execution time Memory
131093 2019-07-16T12:54:32 Z fefe Game (IOI13_game) C++17
63 / 100
 3341 ms 108664 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[100*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 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 372 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 380 KB Output is correct
12 Correct 2 ms 404 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 788 ms 16548 KB Output is correct
5 Correct 509 ms 16120 KB Output is correct
6 Correct 778 ms 13172 KB Output is correct
7 Correct 900 ms 12860 KB Output is correct
8 Correct 563 ms 9056 KB Output is correct
9 Correct 920 ms 13120 KB Output is correct
10 Correct 746 ms 12600 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 380 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 508 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 532 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1200 ms 19560 KB Output is correct
13 Correct 2699 ms 8004 KB Output is correct
14 Correct 435 ms 2076 KB Output is correct
15 Correct 3341 ms 11236 KB Output is correct
16 Correct 272 ms 23576 KB Output is correct
17 Correct 1473 ms 15204 KB Output is correct
18 Correct 2533 ms 24008 KB Output is correct
19 Correct 2130 ms 24100 KB Output is correct
20 Correct 2017 ms 23340 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 580 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 3 ms 376 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 6 ms 376 KB Output is correct
12 Correct 777 ms 16560 KB Output is correct
13 Correct 499 ms 16120 KB Output is correct
14 Correct 779 ms 13240 KB Output is correct
15 Correct 893 ms 12920 KB Output is correct
16 Correct 564 ms 9120 KB Output is correct
17 Correct 900 ms 13064 KB Output is correct
18 Correct 720 ms 12844 KB Output is correct
19 Correct 1205 ms 19016 KB Output is correct
20 Correct 2700 ms 7968 KB Output is correct
21 Correct 435 ms 2172 KB Output is correct
22 Correct 3156 ms 11112 KB Output is correct
23 Correct 267 ms 23544 KB Output is correct
24 Correct 1440 ms 15248 KB Output is correct
25 Correct 2500 ms 23864 KB Output is correct
26 Correct 2156 ms 24200 KB Output is correct
27 Correct 1947 ms 23444 KB Output is correct
28 Runtime error 254 ms 108664 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 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 777 ms 16732 KB Output is correct
13 Correct 502 ms 16304 KB Output is correct
14 Correct 849 ms 13324 KB Output is correct
15 Correct 916 ms 13084 KB Output is correct
16 Correct 562 ms 9224 KB Output is correct
17 Correct 872 ms 13236 KB Output is correct
18 Correct 759 ms 12920 KB Output is correct
19 Correct 1202 ms 19096 KB Output is correct
20 Correct 2715 ms 8052 KB Output is correct
21 Correct 434 ms 2088 KB Output is correct
22 Correct 3184 ms 11356 KB Output is correct
23 Correct 267 ms 23544 KB Output is correct
24 Correct 1496 ms 15308 KB Output is correct
25 Correct 2393 ms 24056 KB Output is correct
26 Correct 2108 ms 24184 KB Output is correct
27 Correct 1895 ms 23416 KB Output is correct
28 Runtime error 254 ms 108644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -