Submission #437524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
437524	2021-06-26T12:29:35 Z	RainAir	Game (IOI13_game)	C++11	100 / 100	8404 ms	31648 KB

game

#include "game.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 700000 + 5;

// fhq treap part

std::mt19937 g(time(0));
int ch[MAXN][2],f[MAXN],id[MAXN],cnt;
LL val[MAXN],sm[MAXN];
unsigned int rnd[MAXN];
#define lc (ch[x][0])
#define rc (ch[x][1])

inline void pushup(int x){
	sm[x] = val[x];
	if(lc) sm[x] = std::__gcd(sm[x],sm[lc]);
	if(rc) sm[x] = std::__gcd(sm[x],sm[rc]);
}

inline void split(int x,int &l,int &r,int k){
	// 划分成 id <= k 的和 > k 的
	if(!x){l = r = 0;return;}
	if(id[x] <= k){
		l = x;split(rc,ch[l][1],r,k);
		pushup(l);
	}
	else{
		r = x;split(lc,l,ch[r][0],k);
		pushup(r);
	}
}

inline int merge(int x,int y){
	if(!x || !y) return x|y;
	if(rnd[x] <= rnd[y]){
		ch[x][1] = merge(ch[x][1],y);
		pushup(x);
		return x;
	}
	else{
		ch[y][0] = merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}

inline LL query1(int &v,int l,int r){
	int a,b,c,d;
	split(v,a,b,l-1);split(b,c,d,r);
	LL ans = sm[c];
	v = merge(a,c);v = merge(v,d);
	return ans;
}

inline void update1(int &v,int p,LL dd){
	int a,b,c,d;
	split(v,a,b,p-1);split(b,c,d,p);
	if(!c){
		c = ++cnt;
		rnd[cnt] = g();
		id[cnt] = p;
		val[cnt] = sm[cnt] = dd;
	}
	else{
		val[c] = sm[c] = dd;
	}
	v = merge(a,c);v = merge(v,d);
}
#undef lc
#undef rc

int n,m;
int rt[MAXN],lc[MAXN],rc[MAXN],tot,R;

inline void pushup(int x,int y){
	LL vl = query1(rt[lc[x]],y,y),vr = query1(rt[rc[x]],y,y);
	update1(rt[x],y,std::__gcd(vl,vr));
}

inline void update(int &x,int l,int r,int p,int y,LL d){
	if(!x) x = ++tot;
	if(l == r){
		update1(rt[x],y,d);
		return;
	}
	int mid = (l + r) >> 1;
	if(p <= mid) update(lc[x],l,mid,p,y,d);
	else update(rc[x],mid+1,r,p,y,d);
	pushup(x,y);
}

inline LL query(int x,int l,int r,int L,int R,int _L,int _R){
	if(!x) return 0;
	if(l == L && r == R) return query1(rt[x],_L,_R);
	int mid = (l + r) >> 1;
	if(R <= mid) return query(lc[x],l,mid,L,R,_L,_R);
	else if(L > mid) return query(rc[x],mid+1,r,L,R,_L,_R);
	else return std::__gcd(query(lc[x],l,mid,L,mid,_L,_R),query(rc[x],mid+1,r,mid+1,R,_L,_R));
}

void init(int R,int C){
	n = R;m = C;
}

void update(int x,int y,LL k){
	++x;++y;
	update(R,1,n,x,y,k);
}

LL calculate(int l1,int l2,int r1,int r2){
	++l1;++r1;++l2;++r2;
	return query(R,1,n,l1,r1,l2,r2);
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	1160 ms	10104 KB	Output is correct
5	Correct	547 ms	9924 KB	Output is correct
6	Correct	1502 ms	7460 KB	Output is correct
7	Correct	1736 ms	7064 KB	Output is correct
8	Correct	1100 ms	6928 KB	Output is correct
9	Correct	1717 ms	7184 KB	Output is correct
10	Correct	1557 ms	6844 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	308 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1851 ms	10848 KB	Output is correct
13	Correct	3729 ms	6260 KB	Output is correct
14	Correct	506 ms	5492 KB	Output is correct
15	Correct	3758 ms	7156 KB	Output is correct
16	Correct	594 ms	8336 KB	Output is correct
17	Correct	2339 ms	8096 KB	Output is correct
18	Correct	4025 ms	9044 KB	Output is correct
19	Correct	3323 ms	9296 KB	Output is correct
20	Correct	3483 ms	8700 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	304 KB	Output is correct
12	Correct	1233 ms	10028 KB	Output is correct
13	Correct	554 ms	9960 KB	Output is correct
14	Correct	1585 ms	7352 KB	Output is correct
15	Correct	1789 ms	7088 KB	Output is correct
16	Correct	1150 ms	6856 KB	Output is correct
17	Correct	1671 ms	7200 KB	Output is correct
18	Correct	1567 ms	6788 KB	Output is correct
19	Correct	1930 ms	10940 KB	Output is correct
20	Correct	3668 ms	6264 KB	Output is correct
21	Correct	536 ms	5620 KB	Output is correct
22	Correct	3878 ms	7188 KB	Output is correct
23	Correct	583 ms	8340 KB	Output is correct
24	Correct	2286 ms	8168 KB	Output is correct
25	Correct	4141 ms	9064 KB	Output is correct
26	Correct	3588 ms	9280 KB	Output is correct
27	Correct	3694 ms	8696 KB	Output is correct
28	Correct	1509 ms	16060 KB	Output is correct
29	Correct	3074 ms	19472 KB	Output is correct
30	Correct	5685 ms	15220 KB	Output is correct
31	Correct	4686 ms	13024 KB	Output is correct
32	Correct	684 ms	4932 KB	Output is correct
33	Correct	1037 ms	5100 KB	Output is correct
34	Correct	812 ms	17472 KB	Output is correct
35	Correct	2652 ms	11336 KB	Output is correct
36	Correct	6018 ms	16672 KB	Output is correct
37	Correct	4737 ms	16720 KB	Output is correct
38	Correct	4844 ms	16044 KB	Output is correct
39	Correct	3694 ms	14228 KB	Output is correct
40	Correct	1 ms	308 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	288 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	2 ms	368 KB	Output is correct
12	Correct	1194 ms	10136 KB	Output is correct
13	Correct	580 ms	9872 KB	Output is correct
14	Correct	1540 ms	7356 KB	Output is correct
15	Correct	1770 ms	7092 KB	Output is correct
16	Correct	1135 ms	6792 KB	Output is correct
17	Correct	1653 ms	7132 KB	Output is correct
18	Correct	1579 ms	6772 KB	Output is correct
19	Correct	1840 ms	10848 KB	Output is correct
20	Correct	3664 ms	6272 KB	Output is correct
21	Correct	516 ms	5504 KB	Output is correct
22	Correct	3847 ms	7300 KB	Output is correct
23	Correct	560 ms	8260 KB	Output is correct
24	Correct	2301 ms	8304 KB	Output is correct
25	Correct	3885 ms	9156 KB	Output is correct
26	Correct	3390 ms	9384 KB	Output is correct
27	Correct	3319 ms	8680 KB	Output is correct
28	Correct	1275 ms	16108 KB	Output is correct
29	Correct	3037 ms	19532 KB	Output is correct
30	Correct	5219 ms	15288 KB	Output is correct
31	Correct	4548 ms	13332 KB	Output is correct
32	Correct	701 ms	5156 KB	Output is correct
33	Correct	1018 ms	5216 KB	Output is correct
34	Correct	884 ms	17500 KB	Output is correct
35	Correct	2589 ms	11416 KB	Output is correct
36	Correct	5646 ms	16580 KB	Output is correct
37	Correct	4375 ms	16716 KB	Output is correct
38	Correct	4604 ms	16180 KB	Output is correct
39	Correct	1961 ms	29788 KB	Output is correct
40	Correct	5060 ms	31648 KB	Output is correct
41	Correct	8404 ms	26192 KB	Output is correct
42	Correct	7151 ms	20832 KB	Output is correct
43	Correct	1881 ms	30952 KB	Output is correct
44	Correct	1125 ms	4704 KB	Output is correct
45	Correct	3356 ms	13688 KB	Output is correct
46	Correct	7687 ms	30052 KB	Output is correct
47	Correct	7631 ms	29984 KB	Output is correct
48	Correct	8101 ms	29604 KB	Output is correct
49	Correct	1 ms	332 KB	Output is correct