Submission #369767

#	Time	Username	Problem	Language	Result	Execution time	Memory
369767		YJU	Collapse (JOI18_collapse)	C++14	5 / 100	15095 ms	75308 KiB

collapse

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<17);
const ld pi=acos(-1);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

vector<ll> ret;

struct TSG{
	ll dir[N],sz[N],stk[N],now;
	void init(){
		REP1(i,N-1)dir[i]=i,sz[i]=1;
		now=0;
	}
	//dsu
	ll find(ll id){
		while(dir[id]!=id)id=dir[id];
		return id;
	}
	void uni(ll x,ll y){
		x=find(x);y=find(y);
		if(x==y){return ;}
		if(sz[x]>sz[y])swap(x,y);
		stk[++now]=x;
		dir[x]=y;
		sz[y]+=sz[x];
	}
	void undo(){
		sz[dir[stk[now]]]-=sz[stk[now]];
		dir[stk[now]]=stk[now];
		--now;
	}
	//append or delete operations
	vector<pll> opr[4*N];
	void _app(ll id,ll l,ll r,ll ql,ll qr,pll o){
		if(l>=ql&&r<=qr){opr[id].pb(o);return ;}
		if(l>=qr||r<=ql)return ;
		ll mid=(l+r)>>1;
		_app(id*2,l,mid,ql,qr,o);
		_app(id*2+1,mid,r,ql,qr,o);
	}
	void app(ll ql,ll qr,pll o){_app(1,0,N,ql,qr,o);return ;}
	void _del(ll id,ll l,ll r,ll ql,ll qr){
		if(l>=ql&&r<=qr){opr[id].resize(SZ(opr[id])-1);return ;}
		if(l>=qr||r<=ql)return ;
		ll mid=(l+r)>>1;
		_del(id*2,l,mid,ql,qr);
		_del(id*2+1,mid,r,ql,qr);
	}
	void del(ll ql,ll qr){_del(1,0,N,ql,qr);return ;}
	//locations of query
	vector<ll> qid[N];
	ll seg[4*N];
	void _ins(ll id,ll l,ll r,ll to,ll ip){
		if(l==r-1){qid[l].pb(ip);seg[id]=SZ(qid[l]);return ;}
		ll mid=(l+r)>>1;
		if(to<mid){
			_ins(id*2,l,mid,to,ip);
		}else{
			_ins(id*2+1,mid,r,to,ip);
		}
		seg[id]=seg[id*2]+seg[id*2+1];
	}
	void ins(ll to,ll ip){_ins(1,0,N,to,ip);return ;}
	//answer
	void build(ll id,ll l,ll r){
		ll st=now;
		for(pll i:opr[id])uni(i.X,i.Y);
		if(l==r-1){
			for(ll i:qid[l])ret[i]=-now;
			qid[l].clear();
			seg[id]=0;
		}
		if(l<r-1){
			ll mid=(l+r)>>1;
			if(seg[id*2])build(id*2,l,mid);
			if(seg[id*2+1])build(id*2+1,mid,r);
			seg[id]=seg[id*2]+seg[id*2+1];
		}
		while(now>st)undo();
	}
}S;

vector<pll> opr[4*N],query[N];
ll sum[4*N];

void add(ll id,ll l,ll r,ll ql,ll qr,pll o){
	if(l>=ql&&r<=qr){opr[id].pb(o);return ;}
	if(l>=qr||r<=ql)return ;
	ll mid=(l+r)>>1;
	add(id*2,l,mid,ql,qr,o);
	add(id*2+1,mid,r,ql,qr,o);
}

void ins(ll id,ll l,ll r,ll to){
	if(l==r-1){++sum[id];return ;}
	ll mid=(l+r)>>1;
	if(to<mid){
		ins(id*2,l,mid,to);
	}else{
		ins(id*2+1,mid,r,to);
	}
	sum[id]=sum[id*2]+sum[id*2+1];
}

void build(ll id,ll l,ll r){
	for(auto i:opr[id]){
		S.app(0,i.X,i);
		S.app(i.Y,N,i);
	}
	if(l==r-1){
		for(auto i:query[l])S.ins(i.X,i.Y);
		if(SZ(query[l]))S.build(1,0,N);
	}else{
		ll mid=(l+r)>>1;
		if(sum[id*2])build(id*2,l,mid);
		if(sum[id*2+1])build(id*2+1,mid,r);
	}
	for(auto i:opr[id]){
		S.del(0,i.X);
		S.del(i.Y,N);
	}
}

ll n,q,c;
map<pll,ll> lst;
 
vector<ll> simulateCollapse(ll _N,vector<ll> ty,vector<ll> x,vector<ll> y,vector<ll> w,vector<ll> p){
	S.init();
	n=_N;q=SZ(w);c=SZ(ty);
	ret.resize(q);
	REP(i,c){
		++x[i];++y[i];
		if(x[i]>y[i])swap(x[i],y[i]);
		if(ty[i]==0){
			lst[mp(x[i],y[i])]=i;
		}else{
			auto it=lst.find(mp(x[i],y[i]));
			add(1,0,N,lst[mp(x[i],y[i])],i,mp(x[i],y[i]));
			lst.erase(it);
		}
	}
	for(auto i:lst){add(1,0,N,i.Y,c,i.X);}
	REP(i,q){
		++p[i];
		ins(1,0,N,w[i]);
		query[w[i]].pb(mp(p[i],i));
	}
	build(1,0,N);
	REP(i,q)ret[i]+=n;
	return ret;
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	vector<ll> T={0,0,0,0};
	vector<ll> TX={0,1,2,4};
	vector<ll> TY={1,3,4,0};
	vector<ll> W={3};
	vector<ll> P={1};
	vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
	for(auto i:ans)cout<<i<<"\n";
	return 0;
}

//*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35