oj.uz

Submission #369760

# Submission time Handle Problem Language Result Execution time Memory
369760 2021-02-22T11:32:19 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 173596 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<<19);
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];

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 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;
		build(id*2,l,mid);
		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];
		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 101 ms 128108 KB Output is correct
2 Correct 98 ms 127816 KB Output is correct
3 Correct 97 ms 127852 KB Output is correct
4 Correct 98 ms 127852 KB Output is correct
5 Correct 110 ms 128236 KB Output is correct
6 Correct 186 ms 130156 KB Output is correct
7 Correct 97 ms 128000 KB Output is correct
8 Correct 97 ms 127980 KB Output is correct
9 Correct 114 ms 128660 KB Output is correct
10 Correct 153 ms 129004 KB Output is correct
11 Correct 304 ms 130156 KB Output is correct
12 Correct 267 ms 130156 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 131680 KB Output is correct
2 Correct 141 ms 131692 KB Output is correct
3 Correct 444 ms 141516 KB Output is correct
4 Correct 134 ms 131820 KB Output is correct
5 Correct 625 ms 143084 KB Output is correct
6 Correct 214 ms 134380 KB Output is correct
7 Correct 12479 ms 173596 KB Output is correct
8 Correct 734 ms 144620 KB Output is correct
9 Correct 140 ms 132064 KB Output is correct
10 Correct 136 ms 131692 KB Output is correct
11 Correct 154 ms 132752 KB Output is correct
12 Correct 839 ms 147388 KB Output is correct
13 Execution timed out 15032 ms 159064 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 131680 KB Output is correct
2 Correct 136 ms 131344 KB Output is correct
3 Correct 139 ms 131612 KB Output is correct
4 Correct 143 ms 131844 KB Output is correct
5 Correct 154 ms 131948 KB Output is correct
6 Correct 457 ms 134252 KB Output is correct
7 Correct 10633 ms 164940 KB Output is correct
8 Execution timed out 15089 ms 164312 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 128108 KB Output is correct
2 Correct 98 ms 127816 KB Output is correct
3 Correct 97 ms 127852 KB Output is correct
4 Correct 98 ms 127852 KB Output is correct
5 Correct 110 ms 128236 KB Output is correct
6 Correct 186 ms 130156 KB Output is correct
7 Correct 97 ms 128000 KB Output is correct
8 Correct 97 ms 127980 KB Output is correct
9 Correct 114 ms 128660 KB Output is correct
10 Correct 153 ms 129004 KB Output is correct
11 Correct 304 ms 130156 KB Output is correct
12 Correct 267 ms 130156 KB Output is correct
13 Correct 136 ms 131680 KB Output is correct
14 Correct 141 ms 131692 KB Output is correct
15 Correct 444 ms 141516 KB Output is correct
16 Correct 134 ms 131820 KB Output is correct
17 Correct 625 ms 143084 KB Output is correct
18 Correct 214 ms 134380 KB Output is correct
19 Correct 12479 ms 173596 KB Output is correct
20 Correct 734 ms 144620 KB Output is correct
21 Correct 140 ms 132064 KB Output is correct
22 Correct 136 ms 131692 KB Output is correct
23 Correct 154 ms 132752 KB Output is correct
24 Correct 839 ms 147388 KB Output is correct
25 Execution timed out 15032 ms 159064 KB Time limit exceeded
26 Halted 0 ms 0 KB -