oj.uz

Submission #94368

# Submission time Handle Problem Language Result Execution time Memory
94368 2019-01-18T02:04:53 Z fjzzq2002 Game (IOI13_game) C++14
80 / 100
 13000 ms 27336 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)
{
	ull t;
	while(b)
		t=a%b,a=b,b=t;
	return a;
	/*
    #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];
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]]);
}
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]=x*P+y;
	else assert(sz[B]==1);
	vv[B]=ss[B]=v;
	B=merge(B,C);
	u=merge(A,B);
}
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:81:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(!x) x=++sn; edt(seg_ps[x],q,p,v);
  ^~
game.cpp:81: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 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 3 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 1407 ms 9728 KB Output is correct
5 Correct 676 ms 10108 KB Output is correct
6 Correct 1657 ms 7636 KB Output is correct
7 Correct 1894 ms 7544 KB Output is correct
8 Correct 1348 ms 7172 KB Output is correct
9 Correct 1834 ms 7512 KB Output is correct
10 Correct 1739 ms 7160 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 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 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 3 ms 376 KB Output is correct
12 Correct 2557 ms 11980 KB Output is correct
13 Correct 6012 ms 7968 KB Output is correct
14 Correct 947 ms 5772 KB Output is correct
15 Correct 6566 ms 8828 KB Output is correct
16 Correct 626 ms 9680 KB Output is correct
17 Correct 2999 ms 8568 KB Output is correct
18 Correct 5314 ms 11120 KB Output is correct
19 Correct 4455 ms 11228 KB Output is correct
20 Correct 5086 ms 10544 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 18 ms 540 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 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 3 ms 376 KB Output is correct
12 Correct 1418 ms 9580 KB Output is correct
13 Correct 689 ms 10076 KB Output is correct
14 Correct 1683 ms 7756 KB Output is correct
15 Correct 1885 ms 7416 KB Output is correct
16 Correct 1361 ms 7068 KB Output is correct
17 Correct 1771 ms 7564 KB Output is correct
18 Correct 1747 ms 7092 KB Output is correct
19 Correct 2568 ms 12448 KB Output is correct
20 Correct 6013 ms 7988 KB Output is correct
21 Correct 947 ms 5840 KB Output is correct
22 Correct 6608 ms 9020 KB Output is correct
23 Correct 626 ms 9716 KB Output is correct
24 Correct 3022 ms 8744 KB Output is correct
25 Correct 4975 ms 11200 KB Output is correct
26 Correct 4286 ms 11308 KB Output is correct
27 Correct 5026 ms 10688 KB Output is correct
28 Correct 10655 ms 24812 KB Output is correct
29 Correct 3325 ms 27240 KB Output is correct
30 Correct 8141 ms 20220 KB Output is correct
31 Correct 6967 ms 17236 KB Output is correct
32 Correct 1254 ms 10656 KB Output is correct
33 Correct 1856 ms 10840 KB Output is correct
34 Correct 742 ms 20976 KB Output is correct
35 Correct 3232 ms 18236 KB Output is correct
36 Correct 6393 ms 25092 KB Output is correct
37 Correct 4984 ms 25164 KB Output is correct
38 Correct 5976 ms 24836 KB Output is correct
39 Correct 4297 ms 21868 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 376 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 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 3 ms 376 KB Output is correct
12 Correct 1415 ms 9880 KB Output is correct
13 Correct 687 ms 10092 KB Output is correct
14 Correct 1651 ms 7728 KB Output is correct
15 Correct 1881 ms 7476 KB Output is correct
16 Correct 1363 ms 7016 KB Output is correct
17 Correct 1806 ms 7632 KB Output is correct
18 Correct 1759 ms 7264 KB Output is correct
19 Correct 2620 ms 12316 KB Output is correct
20 Correct 6013 ms 7880 KB Output is correct
21 Correct 937 ms 5752 KB Output is correct
22 Correct 6510 ms 8860 KB Output is correct
23 Correct 633 ms 9588 KB Output is correct
24 Correct 2942 ms 8684 KB Output is correct
25 Correct 5106 ms 11012 KB Output is correct
26 Correct 4455 ms 11184 KB Output is correct
27 Correct 4994 ms 10716 KB Output is correct
28 Correct 11234 ms 24876 KB Output is correct
29 Correct 3317 ms 27336 KB Output is correct
30 Correct 8374 ms 20068 KB Output is correct
31 Correct 7107 ms 17076 KB Output is correct
32 Correct 1289 ms 10492 KB Output is correct
33 Correct 1878 ms 10948 KB Output is correct
34 Correct 732 ms 21020 KB Output is correct
35 Correct 3432 ms 18032 KB Output is correct
36 Correct 6554 ms 25308 KB Output is correct
37 Correct 4811 ms 25352 KB Output is correct
38 Correct 5622 ms 24692 KB Output is correct
39 Execution timed out 13069 ms 18648 KB Time limit exceeded
40 Halted 0 ms 0 KB -