oj.uz

Submission #122145

# Submission time Handle Problem Language Result Execution time Memory
122145 2019-06-27T17:09:37 Z yusufake Game (IOI13_game) C++
100 / 100
 7558 ms 49488 KB 
#include <bits/stdc++.h>
#include "game.h"
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
 
const int MAXR=1e9,MAXC=1e9;
const int MAX1=40*22000,MAX2=20*20*22000;
 
int root[MAX1],cl2[MAX2],cr2[MAX2],l2[MAX2],r2[MAX2];
int cl1[MAX1],cr1[MAX1],tme1,tme2,ROOT;
LL f[MAX2];
 
long long gcd2(long long X, long long Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
int newNode1() {
 
	int v=++tme1;
	root[tme1]=++tme2;
	l2[tme2]=0; r2[tme2]=MAXC-1;
	return v;
 
}
 
int newNode2(int l,int r) {
 
	int v=++tme2;
	l2[v]=l; r2[v]=r;
	return v;
 
}
 
void init(int r,int c) {
 
	ROOT=newNode1();
 
}
 
LL que2(int x,int l,int r) {
 
	if(x==0||l2[x]>r||r2[x]<l) 
		return 0; 
	if(l2[x]>=l&&r2[x]<=r)
		return f[x];
	return gcd2(que2(cl2[x],l,r),que2(cr2[x],l,r));
 
}
 
LL que1(int x,int l,int r,int ll,int rr,int xx,int yy) {
 
	if(l>rr||r<ll||x==0)
		return 0;
	if(l>=ll&&r<=rr)
		return que2(root[x],xx,yy);
	int md=(l+r)/2;
	return gcd2(que1(cl1[x],l,md,ll,rr,xx,yy),que1(cr1[x],md+1,r,ll,rr,xx,yy));
 
}
 
void upd2(int x,int y,LL k) {
	//cout<<"upd2: "<<x<<" "<<l2[x]<<" "<<r2[x]<<endl;
	if(l2[x]==y&&r2[x]==y) {
		f[x]=k;
		return;
	}
	int mdo=(l2[x]+r2[x])/2;
	int &v=(y<=mdo?cl2[x]:cr2[x]);
	if(v==0) {
		v=newNode2(y,y);
		f[v]=k;
	}
	else if(l2[v]<=y&&r2[v]>=y) 
		upd2(v,y,k);
	else {
		//cout<<"oh no "<<l2[v]<<" "<<r2[v]<<" "<<y<<endl;
		int l=l2[x],r=r2[x],md=(l2[x]+r2[x])/2,t=v;
		do {
			if(y<=md) 
				r=md;
			else l=md+1;
			md=(l+r)/2;
		} while((y<=md)==(l2[v]<=md));
		//cout<<l<<" "<<r<<endl;
		int nw=newNode2(l,r);
		v=nw;
		if(l2[t]<=md) cl2[nw]=t;
		else cr2[nw]=t;
		upd2(nw,y,k);
	}
	f[x]=gcd2(f[cl2[x]],f[cr2[x]]);
 
}
 
void upd1(int &x,int l,int r,int ll,int y,LL k) {
 
	if(x==0) 
		x=newNode1();
	if(l==r) {
		upd2(root[x],y,k);
		return;
	}
	int md=(l+r)/2;
	if(ll<=md)
		upd1(cl1[x],l,md,ll,y,k);
	else upd1(cr1[x],md+1,r,ll,y,k);
	upd2(root[x],y,gcd2(que2(root[cl1[x]],y,y),que2(root[cr1[x]],y,y)));
 
}
 
void update(int x,int y,LL k) {
 
	upd1(ROOT,0,MAXR-1,x,y,k);
 
}
 
LL calculate(int p,int q,int u,int v) {
 
	return que1(ROOT,0,MAXR-1,p,u,q,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 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 903 ms 19052 KB Output is correct
5 Correct 563 ms 19368 KB Output is correct
6 Correct 1170 ms 16308 KB Output is correct
7 Correct 1461 ms 16032 KB Output is correct
8 Correct 682 ms 9584 KB Output is correct
9 Correct 1333 ms 16052 KB Output is correct
10 Correct 1195 ms 15864 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1105 ms 9884 KB Output is correct
13 Correct 2226 ms 4824 KB Output is correct
14 Correct 358 ms 2040 KB Output is correct
15 Correct 2541 ms 6320 KB Output is correct
16 Correct 411 ms 8520 KB Output is correct
17 Correct 1186 ms 6804 KB Output is correct
18 Correct 2091 ms 8812 KB Output is correct
19 Correct 2028 ms 8900 KB Output is correct
20 Correct 1574 ms 8556 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 957 ms 19120 KB Output is correct
13 Correct 583 ms 19244 KB Output is correct
14 Correct 1117 ms 16244 KB Output is correct
15 Correct 1345 ms 15920 KB Output is correct
16 Correct 711 ms 9592 KB Output is correct
17 Correct 1428 ms 16188 KB Output is correct
18 Correct 1145 ms 15860 KB Output is correct
19 Correct 1053 ms 9700 KB Output is correct
20 Correct 2147 ms 5016 KB Output is correct
21 Correct 353 ms 2076 KB Output is correct
22 Correct 2664 ms 6284 KB Output is correct
23 Correct 409 ms 8600 KB Output is correct
24 Correct 1199 ms 6396 KB Output is correct
25 Correct 2103 ms 8632 KB Output is correct
26 Correct 1972 ms 8712 KB Output is correct
27 Correct 1810 ms 8352 KB Output is correct
28 Correct 671 ms 18652 KB Output is correct
29 Correct 2013 ms 21116 KB Output is correct
30 Correct 4467 ms 15452 KB Output is correct
31 Correct 3797 ms 12252 KB Output is correct
32 Correct 412 ms 1808 KB Output is correct
33 Correct 584 ms 2260 KB Output is correct
34 Correct 305 ms 18120 KB Output is correct
35 Correct 1352 ms 10728 KB Output is correct
36 Correct 3031 ms 18440 KB Output is correct
37 Correct 2419 ms 18320 KB Output is correct
38 Correct 2333 ms 17756 KB Output is correct
39 Correct 1816 ms 14440 KB Output is correct
40 Correct 2 ms 428 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 360 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 965 ms 18584 KB Output is correct
13 Correct 614 ms 18772 KB Output is correct
14 Correct 1287 ms 15640 KB Output is correct
15 Correct 1515 ms 15376 KB Output is correct
16 Correct 722 ms 8944 KB Output is correct
17 Correct 1475 ms 15244 KB Output is correct
18 Correct 1119 ms 15096 KB Output is correct
19 Correct 1038 ms 9324 KB Output is correct
20 Correct 2114 ms 4412 KB Output is correct
21 Correct 351 ms 1140 KB Output is correct
22 Correct 2558 ms 5676 KB Output is correct
23 Correct 441 ms 7644 KB Output is correct
24 Correct 1266 ms 5948 KB Output is correct
25 Correct 2374 ms 7908 KB Output is correct
26 Correct 1894 ms 8108 KB Output is correct
27 Correct 1673 ms 7544 KB Output is correct
28 Correct 637 ms 17820 KB Output is correct
29 Correct 1946 ms 20668 KB Output is correct
30 Correct 4553 ms 15376 KB Output is correct
31 Correct 4105 ms 11972 KB Output is correct
32 Correct 425 ms 1272 KB Output is correct
33 Correct 597 ms 1784 KB Output is correct
34 Correct 319 ms 17708 KB Output is correct
35 Correct 1577 ms 10160 KB Output is correct
36 Correct 3248 ms 18060 KB Output is correct
37 Correct 2503 ms 18220 KB Output is correct
38 Correct 2378 ms 17552 KB Output is correct
39 Correct 873 ms 42616 KB Output is correct
40 Correct 3622 ms 49488 KB Output is correct
41 Correct 7558 ms 38860 KB Output is correct
42 Correct 6456 ms 31212 KB Output is correct
43 Correct 810 ms 44408 KB Output is correct
44 Correct 530 ms 10716 KB Output is correct
45 Correct 1833 ms 24420 KB Output is correct
46 Correct 4166 ms 48236 KB Output is correct
47 Correct 4318 ms 48268 KB Output is correct
48 Correct 3769 ms 47968 KB Output is correct
49 Correct 2 ms 256 KB Output is correct