oj.uz

Submission #369778

# Submission time Handle Problem Language Result Execution time Memory
369778 2021-02-22T11:52:15 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 76972 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 n;
	ll dir[N],sz[N],stk[N],now;
	void init(ll _n){
		n=_n;
		REP1(i,n)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,1,n+1,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,1,n+1,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,1,n+1,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]=n-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,S.n+1,i);
	}
	if(l==r-1){
		for(auto i:query[l])S.ins(i.X,i.Y);
		if(SZ(query[l]))S.build(1,1,S.n+1);
	}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,S.n+1);
	}
}

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){
	n=_N;q=SZ(w);c=SZ(ty);
	ret.resize(q);S.init(n);
	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,c+1,lst[mp(x[i],y[i])],i,mp(x[i],y[i]));
			lst.erase(it);
		}
	}
	for(auto i:lst){add(1,0,c+1,i.Y,c,i.X);}
	REP(i,q){
		++p[i];
		ins(1,0,c+1,w[i]);
		query[w[i]].pb(mp(p[i],i));
	}
	build(1,0,c+1);
	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 25 ms 31596 KB Output is correct
2 Correct 21 ms 31340 KB Output is correct
3 Correct 21 ms 31340 KB Output is correct
4 Correct 22 ms 31340 KB Output is correct
5 Correct 28 ms 31724 KB Output is correct
6 Correct 81 ms 33132 KB Output is correct
7 Correct 22 ms 31596 KB Output is correct
8 Correct 26 ms 31596 KB Output is correct
9 Correct 35 ms 32108 KB Output is correct
10 Correct 72 ms 32492 KB Output is correct
11 Correct 221 ms 33772 KB Output is correct
12 Correct 189 ms 33684 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 34784 KB Output is correct
2 Correct 55 ms 34796 KB Output is correct
3 Correct 211 ms 44636 KB Output is correct
4 Correct 55 ms 34796 KB Output is correct
5 Correct 373 ms 46060 KB Output is correct
6 Correct 120 ms 36716 KB Output is correct
7 Correct 11792 ms 76972 KB Output is correct
8 Correct 594 ms 47084 KB Output is correct
9 Correct 61 ms 35552 KB Output is correct
10 Correct 63 ms 35308 KB Output is correct
11 Correct 93 ms 36204 KB Output is correct
12 Correct 750 ms 50284 KB Output is correct
13 Execution timed out 15009 ms 64244 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 34784 KB Output is correct
2 Correct 54 ms 34412 KB Output is correct
3 Correct 56 ms 34668 KB Output is correct
4 Correct 60 ms 34796 KB Output is correct
5 Correct 86 ms 34796 KB Output is correct
6 Correct 328 ms 36716 KB Output is correct
7 Correct 10357 ms 66932 KB Output is correct
8 Execution timed out 15025 ms 73028 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31596 KB Output is correct
2 Correct 21 ms 31340 KB Output is correct
3 Correct 21 ms 31340 KB Output is correct
4 Correct 22 ms 31340 KB Output is correct
5 Correct 28 ms 31724 KB Output is correct
6 Correct 81 ms 33132 KB Output is correct
7 Correct 22 ms 31596 KB Output is correct
8 Correct 26 ms 31596 KB Output is correct
9 Correct 35 ms 32108 KB Output is correct
10 Correct 72 ms 32492 KB Output is correct
11 Correct 221 ms 33772 KB Output is correct
12 Correct 189 ms 33684 KB Output is correct
13 Correct 53 ms 34784 KB Output is correct
14 Correct 55 ms 34796 KB Output is correct
15 Correct 211 ms 44636 KB Output is correct
16 Correct 55 ms 34796 KB Output is correct
17 Correct 373 ms 46060 KB Output is correct
18 Correct 120 ms 36716 KB Output is correct
19 Correct 11792 ms 76972 KB Output is correct
20 Correct 594 ms 47084 KB Output is correct
21 Correct 61 ms 35552 KB Output is correct
22 Correct 63 ms 35308 KB Output is correct
23 Correct 93 ms 36204 KB Output is correct
24 Correct 750 ms 50284 KB Output is correct
25 Execution timed out 15009 ms 64244 KB Time limit exceeded
26 Halted 0 ms 0 KB -