oj.uz

답안 #437524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437524 2021-06-26T12:29:35 Z RainAir 게임 (IOI13_game) C++11
100 / 100
 8404 ms 31648 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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