oj.uz

Submission #94375

# Submission time Handle Problem Language Result Execution time Memory
94375 2019-01-18T02:21:26 Z fjzzq2002 Game (IOI13_game) C++14
100 / 100
 7109 ms 51516 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ull gcd(ull a,ull b)
{
	if(a==0||b==0) return a^b;
    #define ctz __builtin_ctzll
    int shift = ctz(a | b);
    b >>= ctz(b);
    while (a) {
        a >>= ctz(a);
        if (a < b) swap(a, b);
        a -= b;
    }
    return b << shift;
    #undef ctz
}
 
#define SS 2600003
int an=0,ch[SS][2],sz[SS],RR;
ull vv[SS],ss[SS];
ll xx[SS],L[SS],R[SS];
void upd(int x)
{
	sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
	ss[x]=gcd(gcd(vv[x],ss[ch[x][0]]),ss[ch[x][1]]);
	L[x]=ch[x][0]?L[ch[x][0]]:xx[x];
	R[x]=ch[x][1]?R[ch[x][1]]:xx[x];
}
#define rnd rand
int merge(int a,int b)
{
	if(a&&b);else return a^b;
	if(rnd()%(sz[a]+sz[b])<sz[a])
	{
		ch[a][1]=merge(ch[a][1],b),upd(a);
		return a;
	}
	else
	{
		ch[b][0]=merge(a,ch[b][0]),upd(b);
		return b;
	}
}
void split(int x,ll u,int& a,int& b)
{
	if(x==0) {a=b=0; return;}
	if(xx[x]<=u)
		a=x, split(ch[a][1],u,ch[a][1],b), upd(a);
	else
		b=x, split(ch[b][0],u,a,ch[b][0]), upd(b);
}
const ll P=1.01e9;
void edt(int& u,int x,int y,ull v)
{
	int A,B,C;
	split(u,x*P+y-1,A,B);
	split(B,x*P+y,B,C);
	if(!B) B=++an,sz[B]=1,xx[B]=L[B]=R[B]=x*P+y;
	else assert(sz[B]==1);
	vv[B]=ss[B]=v;
	B=merge(B,C);
	u=merge(A,B);
}
inline ull calc(int u,ll l,ll r)
{
	if(!u||R[u]<l||r<L[u]) return 0;
	if(l<=L[u]&&R[u]<=r) return ss[u];
	ull t=0;
	if(l<=xx[u]&&xx[u]<=r) t=vv[u];
	t=gcd(t,calc(ch[u][0],l,r));
	if(t==1) return 1;
	return gcd(t,calc(ch[u][1],l,r));
}
inline ull qry(int& u,int l,int r)
{return calc(u,l*P,r*P+P-1);}
int seg_ch[SS][2],seg_ps[SS],sn=0,ro;
void edt(int& x,int l,int r,int p,int q,ull v)
{
	if(!x) x=++sn; edt(seg_ps[x],q,p,v);
	if(l==r) return;
	int m=(l+r)>>1;
	if(p<=m) edt(seg_ch[x][0],l,m,p,q,v);
	else edt(seg_ch[x][1],m+1,r,p,q,v);
}
ull qry(int x,int l,int r,int pl,int pr,int sl,int sr)
{
	if(r<pl||pr<l||!x||pl>pr) return 0;
	if(pl<=l&&r<=pr) return qry(seg_ps[x],sl,sr);
	int m=(l+r)>>1;
	return gcd(qry(seg_ch[x][0],l,m,pl,pr,sl,sr),
	qry(seg_ch[x][1],m+1,r,pl,pr,sl,sr));
}
 
void init(int R_, int C_) {
	RR=R_;
}
 
void update(int P, int Q, long long K) {
	edt(ro,0,RR-1,P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
	return qry(ro,0,RR-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;
      ^~~
game.cpp: In function 'void edt(int&, int, int, int, int, ull)':
game.cpp:82:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(!x) x=++sn; edt(seg_ps[x],q,p,v);
  ^~
game.cpp:82:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(!x) x=++sn; edt(seg_ps[x],q,p,v);
                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 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 7 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 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 380 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 645 ms 6884 KB Output is correct
5 Correct 293 ms 8824 KB Output is correct
6 Correct 884 ms 5816 KB Output is correct
7 Correct 1109 ms 5620 KB Output is correct
8 Correct 491 ms 5168 KB Output is correct
9 Correct 984 ms 5624 KB Output is correct
10 Correct 750 ms 5240 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 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 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 1030 ms 10844 KB Output is correct
13 Correct 2334 ms 7212 KB Output is correct
14 Correct 396 ms 3192 KB Output is correct
15 Correct 2529 ms 7760 KB Output is correct
16 Correct 452 ms 9340 KB Output is correct
17 Correct 1263 ms 6856 KB Output is correct
18 Correct 2241 ms 9724 KB Output is correct
19 Correct 1810 ms 9804 KB Output is correct
20 Correct 1519 ms 9268 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.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 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 380 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 376 KB Output is correct
12 Correct 654 ms 6876 KB Output is correct
13 Correct 302 ms 8952 KB Output is correct
14 Correct 896 ms 5880 KB Output is correct
15 Correct 1073 ms 5576 KB Output is correct
16 Correct 495 ms 5488 KB Output is correct
17 Correct 938 ms 5624 KB Output is correct
18 Correct 714 ms 5368 KB Output is correct
19 Correct 1054 ms 12048 KB Output is correct
20 Correct 2384 ms 7160 KB Output is correct
21 Correct 402 ms 3196 KB Output is correct
22 Correct 2564 ms 7700 KB Output is correct
23 Correct 475 ms 9336 KB Output is correct
24 Correct 1107 ms 6760 KB Output is correct
25 Correct 2187 ms 9676 KB Output is correct
26 Correct 1849 ms 9876 KB Output is correct
27 Correct 1495 ms 9228 KB Output is correct
28 Correct 599 ms 20828 KB Output is correct
29 Correct 1712 ms 23896 KB Output is correct
30 Correct 3621 ms 19804 KB Output is correct
31 Correct 3078 ms 15780 KB Output is correct
32 Correct 784 ms 3544 KB Output is correct
33 Correct 866 ms 4028 KB Output is correct
34 Correct 557 ms 20904 KB Output is correct
35 Correct 1360 ms 12664 KB Output is correct
36 Correct 3166 ms 21368 KB Output is correct
37 Correct 2519 ms 21544 KB Output is correct
38 Correct 2033 ms 20916 KB Output is correct
39 Correct 1990 ms 17288 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
20.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 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 380 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 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 654 ms 6560 KB Output is correct
13 Correct 316 ms 8832 KB Output is correct
14 Correct 868 ms 5752 KB Output is correct
15 Correct 1083 ms 5696 KB Output is correct
16 Correct 494 ms 5384 KB Output is correct
17 Correct 985 ms 5644 KB Output is correct
18 Correct 741 ms 5160 KB Output is correct
19 Correct 1051 ms 11916 KB Output is correct
20 Correct 2392 ms 7240 KB Output is correct
21 Correct 397 ms 3092 KB Output is correct
22 Correct 2560 ms 7620 KB Output is correct
23 Correct 504 ms 9336 KB Output is correct
24 Correct 1106 ms 6744 KB Output is correct
25 Correct 2219 ms 9864 KB Output is correct
26 Correct 1844 ms 9908 KB Output is correct
27 Correct 1556 ms 9180 KB Output is correct
28 Correct 606 ms 20632 KB Output is correct
29 Correct 1762 ms 23908 KB Output is correct
30 Correct 3665 ms 19960 KB Output is correct
31 Correct 3121 ms 15872 KB Output is correct
32 Correct 767 ms 3400 KB Output is correct
33 Correct 831 ms 4060 KB Output is correct
34 Correct 518 ms 20900 KB Output is correct
35 Correct 1299 ms 12696 KB Output is correct
36 Correct 3520 ms 21240 KB Output is correct
37 Correct 2519 ms 21252 KB Output is correct
38 Correct 2086 ms 20524 KB Output is correct
39 Correct 895 ms 40672 KB Output is correct
40 Correct 3389 ms 42056 KB Output is correct
41 Correct 7109 ms 39868 KB Output is correct
42 Correct 6279 ms 36144 KB Output is correct
43 Correct 1452 ms 47360 KB Output is correct
44 Correct 1839 ms 12024 KB Output is correct
45 Correct 1833 ms 25592 KB Output is correct
46 Correct 4616 ms 51472 KB Output is correct
47 Correct 5321 ms 51516 KB Output is correct
48 Correct 4327 ms 51224 KB Output is correct
49 Correct 2 ms 376 KB Output is correct