oj.uz

Submission #369766

# Submission time Handle Problem Language Result Execution time Memory
369766 2021-02-22T11:41:47 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 75424 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
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 25 ms 32364 KB Output is correct
3 Correct 25 ms 32364 KB Output is correct
4 Correct 25 ms 32364 KB Output is correct
5 Correct 36 ms 32748 KB Output is correct
6 Correct 104 ms 34412 KB Output is correct
7 Correct 26 ms 32620 KB Output is correct
8 Correct 26 ms 32492 KB Output is correct
9 Correct 40 ms 33132 KB Output is correct
10 Correct 78 ms 33516 KB Output is correct
11 Correct 232 ms 34540 KB Output is correct
12 Correct 193 ms 34540 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 35808 KB Output is correct
2 Correct 72 ms 35820 KB Output is correct
3 Correct 373 ms 45420 KB Output is correct
4 Correct 75 ms 35948 KB Output is correct
5 Correct 541 ms 46956 KB Output is correct
6 Correct 151 ms 38124 KB Output is correct
7 Correct 11737 ms 75424 KB Output is correct
8 Correct 660 ms 47980 KB Output is correct
9 Correct 78 ms 35808 KB Output is correct
10 Correct 75 ms 35564 KB Output is correct
11 Correct 98 ms 36332 KB Output is correct
12 Correct 759 ms 50028 KB Output is correct
13 Execution timed out 15087 ms 61348 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 35808 KB Output is correct
2 Correct 73 ms 35564 KB Output is correct
3 Correct 75 ms 35820 KB Output is correct
4 Correct 78 ms 35948 KB Output is correct
5 Correct 93 ms 35820 KB Output is correct
6 Correct 374 ms 37996 KB Output is correct
7 Correct 10028 ms 66792 KB Output is correct
8 Execution timed out 15091 ms 66600 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 25 ms 32364 KB Output is correct
3 Correct 25 ms 32364 KB Output is correct
4 Correct 25 ms 32364 KB Output is correct
5 Correct 36 ms 32748 KB Output is correct
6 Correct 104 ms 34412 KB Output is correct
7 Correct 26 ms 32620 KB Output is correct
8 Correct 26 ms 32492 KB Output is correct
9 Correct 40 ms 33132 KB Output is correct
10 Correct 78 ms 33516 KB Output is correct
11 Correct 232 ms 34540 KB Output is correct
12 Correct 193 ms 34540 KB Output is correct
13 Correct 72 ms 35808 KB Output is correct
14 Correct 72 ms 35820 KB Output is correct
15 Correct 373 ms 45420 KB Output is correct
16 Correct 75 ms 35948 KB Output is correct
17 Correct 541 ms 46956 KB Output is correct
18 Correct 151 ms 38124 KB Output is correct
19 Correct 11737 ms 75424 KB Output is correct
20 Correct 660 ms 47980 KB Output is correct
21 Correct 78 ms 35808 KB Output is correct
22 Correct 75 ms 35564 KB Output is correct
23 Correct 98 ms 36332 KB Output is correct
24 Correct 759 ms 50028 KB Output is correct
25 Execution timed out 15087 ms 61348 KB Time limit exceeded
26 Halted 0 ms 0 KB -