Submission #437524

#	Time	Username	Problem	Language	Result	Execution time	Memory
437524		RainAir	게임 (IOI13_game)	C++11	100 / 100	8404 ms	31648 KiB

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20