oj.uz

Submission #369764

# Submission time Handle Problem Language Result Execution time Memory
369764 2021-02-22T11:40:05 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 107776 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<<18);
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 52 ms 64492 KB Output is correct
2 Correct 48 ms 64236 KB Output is correct
3 Correct 47 ms 64236 KB Output is correct
4 Correct 47 ms 64236 KB Output is correct
5 Correct 58 ms 64620 KB Output is correct
6 Correct 132 ms 66284 KB Output is correct
7 Correct 48 ms 64432 KB Output is correct
8 Correct 49 ms 64364 KB Output is correct
9 Correct 69 ms 64916 KB Output is correct
10 Correct 105 ms 65356 KB Output is correct
11 Correct 257 ms 66412 KB Output is correct
12 Correct 218 ms 66412 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 67680 KB Output is correct
2 Correct 96 ms 67692 KB Output is correct
3 Correct 410 ms 77344 KB Output is correct
4 Correct 96 ms 67852 KB Output is correct
5 Correct 582 ms 78644 KB Output is correct
6 Correct 180 ms 69868 KB Output is correct
7 Correct 12109 ms 107776 KB Output is correct
8 Correct 708 ms 79356 KB Output is correct
9 Correct 97 ms 67680 KB Output is correct
10 Correct 105 ms 67300 KB Output is correct
11 Correct 126 ms 68204 KB Output is correct
12 Correct 811 ms 82028 KB Output is correct
13 Execution timed out 15090 ms 93228 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 67680 KB Output is correct
2 Correct 94 ms 67308 KB Output is correct
3 Correct 102 ms 67564 KB Output is correct
4 Correct 104 ms 67820 KB Output is correct
5 Correct 113 ms 67692 KB Output is correct
6 Correct 417 ms 69868 KB Output is correct
7 Correct 10391 ms 99288 KB Output is correct
8 Execution timed out 15040 ms 98436 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 64492 KB Output is correct
2 Correct 48 ms 64236 KB Output is correct
3 Correct 47 ms 64236 KB Output is correct
4 Correct 47 ms 64236 KB Output is correct
5 Correct 58 ms 64620 KB Output is correct
6 Correct 132 ms 66284 KB Output is correct
7 Correct 48 ms 64432 KB Output is correct
8 Correct 49 ms 64364 KB Output is correct
9 Correct 69 ms 64916 KB Output is correct
10 Correct 105 ms 65356 KB Output is correct
11 Correct 257 ms 66412 KB Output is correct
12 Correct 218 ms 66412 KB Output is correct
13 Correct 113 ms 67680 KB Output is correct
14 Correct 96 ms 67692 KB Output is correct
15 Correct 410 ms 77344 KB Output is correct
16 Correct 96 ms 67852 KB Output is correct
17 Correct 582 ms 78644 KB Output is correct
18 Correct 180 ms 69868 KB Output is correct
19 Correct 12109 ms 107776 KB Output is correct
20 Correct 708 ms 79356 KB Output is correct
21 Correct 97 ms 67680 KB Output is correct
22 Correct 105 ms 67300 KB Output is correct
23 Correct 126 ms 68204 KB Output is correct
24 Correct 811 ms 82028 KB Output is correct
25 Execution timed out 15090 ms 93228 KB Time limit exceeded
26 Halted 0 ms 0 KB -