oj.uz

Submission #369767

# Submission time Handle Problem Language Result Execution time Memory
369767 2021-02-22T11:43:27 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 75308 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32748 KB Output is correct
2 Correct 24 ms 32364 KB Output is correct
3 Correct 25 ms 32492 KB Output is correct
4 Correct 25 ms 32364 KB Output is correct
5 Correct 35 ms 32748 KB Output is correct
6 Correct 102 ms 34412 KB Output is correct
7 Correct 25 ms 32620 KB Output is correct
8 Correct 25 ms 32492 KB Output is correct
9 Correct 39 ms 33132 KB Output is correct
10 Correct 77 ms 33516 KB Output is correct
11 Correct 229 ms 34540 KB Output is correct
12 Correct 196 ms 34668 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 35808 KB Output is correct
2 Correct 66 ms 35820 KB Output is correct
3 Correct 354 ms 45420 KB Output is correct
4 Correct 80 ms 35948 KB Output is correct
5 Correct 538 ms 46828 KB Output is correct
6 Correct 147 ms 37996 KB Output is correct
7 Correct 11847 ms 75308 KB Output is correct
8 Correct 654 ms 47852 KB Output is correct
9 Correct 72 ms 35808 KB Output is correct
10 Correct 68 ms 35564 KB Output is correct
11 Correct 89 ms 36460 KB Output is correct
12 Correct 745 ms 50140 KB Output is correct
13 Execution timed out 15095 ms 61088 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 35936 KB Output is correct
2 Correct 67 ms 35592 KB Output is correct
3 Correct 69 ms 35820 KB Output is correct
4 Correct 68 ms 35948 KB Output is correct
5 Correct 94 ms 35820 KB Output is correct
6 Correct 371 ms 37868 KB Output is correct
7 Correct 10130 ms 66692 KB Output is correct
8 Execution timed out 15027 ms 66596 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32748 KB Output is correct
2 Correct 24 ms 32364 KB Output is correct
3 Correct 25 ms 32492 KB Output is correct
4 Correct 25 ms 32364 KB Output is correct
5 Correct 35 ms 32748 KB Output is correct
6 Correct 102 ms 34412 KB Output is correct
7 Correct 25 ms 32620 KB Output is correct
8 Correct 25 ms 32492 KB Output is correct
9 Correct 39 ms 33132 KB Output is correct
10 Correct 77 ms 33516 KB Output is correct
11 Correct 229 ms 34540 KB Output is correct
12 Correct 196 ms 34668 KB Output is correct
13 Correct 65 ms 35808 KB Output is correct
14 Correct 66 ms 35820 KB Output is correct
15 Correct 354 ms 45420 KB Output is correct
16 Correct 80 ms 35948 KB Output is correct
17 Correct 538 ms 46828 KB Output is correct
18 Correct 147 ms 37996 KB Output is correct
19 Correct 11847 ms 75308 KB Output is correct
20 Correct 654 ms 47852 KB Output is correct
21 Correct 72 ms 35808 KB Output is correct
22 Correct 68 ms 35564 KB Output is correct
23 Correct 89 ms 36460 KB Output is correct
24 Correct 745 ms 50140 KB Output is correct
25 Execution timed out 15095 ms 61088 KB Time limit exceeded
26 Halted 0 ms 0 KB -