oj.uz

Submission #94369

# Submission time Handle Problem Language Result Execution time Memory
94369 2019-01-18T02:10:04 Z fjzzq2002 Game (IOI13_game) C++14
80 / 100
 13000 ms 41904 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],R;
ull vv[SS],ss[SS];
ll xx[SS];
inline 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]]);
}
#define rnd rand
inline 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;
	}
}
inline 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;
inline 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]=x*P+y;
	else assert(sz[B]==1);
	vv[B]=ss[B]=v;
	B=merge(B,C);
	u=merge(A,B);
}
inline ull qry(int& u,int l,int r)
{
	int A,B,C;
	split(u,l*P-1,A,B);
	split(B,r*P+P-1,B,C);
	ull rs=ss[B];
	B=merge(B,C);
	u=merge(A,B);
	return rs;
} 
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_) {
	R=R_;
}
 
void update(int P, int Q, long long K) {
	edt(ro,0,R-1,P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
	return qry(ro,0,R-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:78:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(!x) x=++sn; edt(seg_ps[x],q,p,v);
  ^~
game.cpp:78: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 380 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 256 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 380 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 2 ms 380 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 1610 ms 8832 KB Output is correct
5 Correct 582 ms 8568 KB Output is correct
6 Correct 2532 ms 5220 KB Output is correct
7 Correct 3115 ms 4972 KB Output is correct
8 Correct 1825 ms 4960 KB Output is correct
9 Correct 2881 ms 4988 KB Output is correct
10 Correct 3498 ms 4696 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 428 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 380 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 2708 ms 10864 KB Output is correct
13 Correct 7389 ms 6112 KB Output is correct
14 Correct 969 ms 3244 KB Output is correct
15 Correct 8004 ms 6460 KB Output is correct
16 Correct 1073 ms 7536 KB Output is correct
17 Correct 3624 ms 5884 KB Output is correct
18 Correct 6381 ms 8044 KB Output is correct
19 Correct 5544 ms 8104 KB Output is correct
20 Correct 6711 ms 7708 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 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 2 ms 380 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 1572 ms 8740 KB Output is correct
13 Correct 579 ms 8316 KB Output is correct
14 Correct 2534 ms 5212 KB Output is correct
15 Correct 3154 ms 4996 KB Output is correct
16 Correct 1790 ms 4956 KB Output is correct
17 Correct 2812 ms 5016 KB Output is correct
18 Correct 3366 ms 4740 KB Output is correct
19 Correct 2750 ms 10672 KB Output is correct
20 Correct 7422 ms 6172 KB Output is correct
21 Correct 955 ms 3324 KB Output is correct
22 Correct 7792 ms 6604 KB Output is correct
23 Correct 946 ms 7672 KB Output is correct
24 Correct 3525 ms 5964 KB Output is correct
25 Correct 6881 ms 8028 KB Output is correct
26 Correct 5509 ms 8148 KB Output is correct
27 Correct 6449 ms 7444 KB Output is correct
28 Correct 1965 ms 16156 KB Output is correct
29 Correct 3755 ms 19192 KB Output is correct
30 Correct 10888 ms 15216 KB Output is correct
31 Correct 8963 ms 12464 KB Output is correct
32 Correct 1398 ms 3448 KB Output is correct
33 Correct 2236 ms 3992 KB Output is correct
34 Correct 906 ms 16272 KB Output is correct
35 Correct 3977 ms 10320 KB Output is correct
36 Correct 7512 ms 16688 KB Output is correct
37 Correct 6383 ms 16764 KB Output is correct
38 Correct 7849 ms 16300 KB Output is correct
39 Correct 4846 ms 13824 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

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 256 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 380 KB Output is correct
12 Correct 1575 ms 8436 KB Output is correct
13 Correct 577 ms 8160 KB Output is correct
14 Correct 2451 ms 4984 KB Output is correct
15 Correct 3112 ms 4784 KB Output is correct
16 Correct 1823 ms 4780 KB Output is correct
17 Correct 3011 ms 5036 KB Output is correct
18 Correct 3563 ms 4420 KB Output is correct
19 Correct 2648 ms 10172 KB Output is correct
20 Correct 7336 ms 5948 KB Output is correct
21 Correct 943 ms 2920 KB Output is correct
22 Correct 7902 ms 6268 KB Output is correct
23 Correct 942 ms 7288 KB Output is correct
24 Correct 3474 ms 5524 KB Output is correct
25 Correct 6926 ms 7528 KB Output is correct
26 Correct 5254 ms 7748 KB Output is correct
27 Correct 6514 ms 7096 KB Output is correct
28 Correct 1805 ms 15568 KB Output is correct
29 Correct 3517 ms 18572 KB Output is correct
30 Correct 10378 ms 14656 KB Output is correct
31 Correct 8996 ms 11748 KB Output is correct
32 Correct 1367 ms 2808 KB Output is correct
33 Correct 2228 ms 3096 KB Output is correct
34 Correct 922 ms 15468 KB Output is correct
35 Correct 4016 ms 9512 KB Output is correct
36 Correct 8405 ms 15724 KB Output is correct
37 Correct 6027 ms 15848 KB Output is correct
38 Correct 7453 ms 15032 KB Output is correct
39 Correct 2619 ms 36364 KB Output is correct
40 Correct 6478 ms 41904 KB Output is correct
41 Execution timed out 13007 ms 31528 KB Time limit exceeded
42 Halted 0 ms 0 KB -