oj.uz

Submission #103255

# Submission time Handle Problem Language Result Execution time Memory
103255 2019-03-29T10:51:21 Z fjzzq2002 Game (IOI13_game) C++14
63 / 100
 13000 ms 26116 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(sz[a]>sz[b])
	{
		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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 432 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 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 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 668 ms 11128 KB Output is correct
5 Correct 327 ms 10868 KB Output is correct
6 Correct 888 ms 8328 KB Output is correct
7 Correct 957 ms 8188 KB Output is correct
8 Correct 444 ms 7228 KB Output is correct
9 Correct 884 ms 8388 KB Output is correct
10 Correct 706 ms 7796 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 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 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 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 1210 ms 14012 KB Output is correct
13 Correct 2321 ms 9152 KB Output is correct
14 Correct 373 ms 5872 KB Output is correct
15 Correct 2605 ms 9972 KB Output is correct
16 Correct 546 ms 11632 KB Output is correct
17 Correct 1178 ms 9664 KB Output is correct
18 Correct 2580 ms 12980 KB Output is correct
19 Correct 1978 ms 13140 KB Output is correct
20 Correct 1788 ms 12664 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 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 3 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 4 ms 356 KB Output is correct
12 Correct 739 ms 11000 KB Output is correct
13 Correct 336 ms 10716 KB Output is correct
14 Correct 880 ms 8440 KB Output is correct
15 Correct 1026 ms 8184 KB Output is correct
16 Correct 478 ms 7416 KB Output is correct
17 Correct 864 ms 8324 KB Output is correct
18 Correct 708 ms 7776 KB Output is correct
19 Correct 1055 ms 14172 KB Output is correct
20 Correct 2510 ms 9336 KB Output is correct
21 Correct 415 ms 5884 KB Output is correct
22 Correct 2589 ms 10032 KB Output is correct
23 Correct 505 ms 11532 KB Output is correct
24 Correct 1329 ms 9776 KB Output is correct
25 Correct 2307 ms 12948 KB Output is correct
26 Correct 2123 ms 13052 KB Output is correct
27 Correct 1882 ms 12528 KB Output is correct
28 Execution timed out 13050 ms 25688 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 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 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 598 ms 10968 KB Output is correct
13 Correct 305 ms 10968 KB Output is correct
14 Correct 787 ms 8444 KB Output is correct
15 Correct 1078 ms 8312 KB Output is correct
16 Correct 486 ms 7404 KB Output is correct
17 Correct 935 ms 8184 KB Output is correct
18 Correct 660 ms 7720 KB Output is correct
19 Correct 1274 ms 14144 KB Output is correct
20 Correct 2407 ms 9204 KB Output is correct
21 Correct 402 ms 5852 KB Output is correct
22 Correct 2405 ms 10104 KB Output is correct
23 Correct 449 ms 11600 KB Output is correct
24 Correct 1074 ms 9592 KB Output is correct
25 Correct 2518 ms 13060 KB Output is correct
26 Correct 2122 ms 13176 KB Output is correct
27 Correct 1875 ms 12664 KB Output is correct
28 Execution timed out 13018 ms 26116 KB Time limit exceeded
29 Halted 0 ms 0 KB -