Submission #1047924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047924		moonrabbit2	Sweeping (JOI20_sweeping)	C++17	100 / 100	4022 ms	119524 KiB

sweeping

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
const int N=1500005;
int n,m,m2,q,k=1,t,g[N];
pii arr[N],ans[N];
bool in[N];
pii a[N],R[N];
struct node{
	int prv=0,nxt=0,val=0;
}V[2*N];
pii P[N],V1[N],V2[N];
int sz[N];
set<pii> S1,S2;
pii Get(int idx){
	return {max(a[idx][0],R[g[idx]][0]),max(a[idx][1],R[g[idx]][1])};
}
void SweepH(int L){
	auto iter=S2.upper_bound({L,q+1557});
	int idxL=(*prev(iter))[1];
	int xL=R[idxL][0],yL=R[idxL][1];
	if(n-L<=xL) return;
	S1.erase({R[idxL][0],idxL});
	S2.erase({R[idxL][1],idxL});
	vector<int> nL,nR;
	bool ok=false;
	int Sz=sz[idxL],i=V2[idxL][0],j=V2[idxL][1];
	while(Sz){
		{
			int idx=V[i].val;
			if(Get(idx)[1]>L){
				ok=true;
				break;
			}
			nL.push_back(idx);
			i=V[i].nxt;
			Sz--;
		}
		if(!Sz) break;
		{
			int idx=V[j].val;
			if(Get(idx)[1]<=L) break;
			nR.push_back(idx);
			j=V[j].prv;
			Sz--;
		}
	}
	if(ok){
		if(nL.size()){
			k++;
			V2[k][0]=V2[idxL][0];
			V2[k][1]=V[i].prv;
			V2[idxL][0]=i;
			sort(nL.begin(),nL.end(),[&](int i,int j){
				return P[i][0]<P[j][0];
			});
			for(int i=0;i<(int)nL.size();i++){
				int idx=nL[i];
				if(V1[idxL][0]==P[idx][0]) V1[idxL][0]=V[V1[idxL][0]].nxt;
				if(V1[idxL][1]==P[idx][0]) V1[idxL][1]=V[V1[idxL][1]].prv;
				g[idx]=k;
				int L=V[P[idx][0]].prv,R=V[P[idx][0]].nxt;
				if(L) V[L].nxt=R;
				if(R) V[R].prv=L;
				V[P[idx][0]].prv=V[P[idx][0]].nxt=0;
				if(!V1[k][0]){
					V1[k][0]=V1[k][1]=P[idx][0];
				} else{
					V[V1[k][1]].nxt=P[idx][0];
					V[P[idx][0]].prv=V1[k][1];
					V1[k][1]=P[idx][0];
				}
				sz[idxL]--;
				sz[k]++;
			}
			R[k][0]=n-L;
			R[k][1]=yL;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
		if(sz[idxL]){
			R[idxL][0]=xL;
			R[idxL][1]=L+1;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
	} else{
		if(nR.size()){
			k++;
			V2[k][0]=V[j].nxt;
			V2[k][1]=V2[idxL][1];
			V2[idxL][1]=j;
			sort(nR.begin(),nR.end(),[&](int i,int j){
				return P[i][0]<P[j][0];
			});
			for(int i=0;i<(int)nR.size();i++){
				int idx=nR[i];
				if(V1[idxL][0]==P[idx][0]) V1[idxL][0]=V[V1[idxL][0]].nxt;
				if(V1[idxL][1]==P[idx][0]) V1[idxL][1]=V[V1[idxL][1]].prv;
				g[idx]=k;
				int L=V[P[idx][0]].prv,R=V[P[idx][0]].nxt;
				if(L) V[L].nxt=R;
				if(R) V[R].prv=L;
				V[P[idx][0]].prv=V[P[idx][0]].nxt=0;
				if(!V1[k][0]){
					V1[k][0]=V1[k][1]=P[idx][0];
				} else{
					V[V1[k][1]].nxt=P[idx][0];
					V[P[idx][0]].prv=V1[k][1];
					V1[k][1]=P[idx][0];
				}
				sz[idxL]--;
				sz[k]++;
			}
			R[k][0]=xL;
			R[k][1]=L+1;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
		if(sz[idxL]){
			R[idxL][0]=n-L;
			R[idxL][1]=yL;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
	}
}
void SweepV(int L){
	auto iter=S1.upper_bound({L,q+1557});
	int idxL=(*prev(iter))[1];
	int xL=R[idxL][0],yL=R[idxL][1];
	if(n-L<=yL) return;
	S1.erase({R[idxL][0],idxL});
	S2.erase({R[idxL][1],idxL});
	vector<int> nL,nR;
	bool ok=false;
	int Sz=sz[idxL],i=V1[idxL][0],j=V1[idxL][1];
	while(Sz){
		{
			int idx=V[i].val;
			if(Get(idx)[0]>L){
				ok=true;
				break;
			}
			nL.push_back(idx);
			i=V[i].nxt;
			Sz--;
		}
		if(!Sz) break;
		{
			int idx=V[j].val;
			if(Get(idx)[0]<=L) break;
			nR.push_back(idx);
			j=V[j].prv;
			Sz--;
		}
	}
	if(ok){
		if(nL.size()){
			k++;
			V1[k][0]=V1[idxL][0];
			V1[k][1]=V[i].prv;
			V1[idxL][0]=i;
			sort(nL.begin(),nL.end(),[&](int i,int j){
				return P[i][1]<P[j][1];
			});
			for(int i=0;i<(int)nL.size();i++){
				int idx=nL[i];
				if(V2[idxL][0]==P[idx][1]) V2[idxL][0]=V[V2[idxL][0]].nxt;
				if(V2[idxL][1]==P[idx][1]) V2[idxL][1]=V[V2[idxL][1]].prv;
				g[idx]=k;
				int L=V[P[idx][1]].prv,R=V[P[idx][1]].nxt;
				if(L) V[L].nxt=R;
				if(R) V[R].prv=L;
				V[P[idx][1]].prv=V[P[idx][1]].nxt=0;
				if(!V2[k][0]){
					V2[k][0]=V2[k][1]=P[idx][1];
				} else{
					V[V2[k][1]].nxt=P[idx][1];
					V[P[idx][1]].prv=V2[k][1];
					V2[k][1]=P[idx][1];
				}
				sz[idxL]--;
				sz[k]++;
			}
			R[k][0]=xL;
			R[k][1]=n-L;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
		if(sz[idxL]){
			R[idxL][0]=L+1;
			R[idxL][1]=yL;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
	} else{
		if(nR.size()){
			k++;
			V1[k][0]=V[j].nxt;
			V1[k][1]=V1[idxL][1];
			V1[idxL][1]=j;
			sort(nR.begin(),nR.end(),[&](int i,int j){
				return P[i][1]<P[j][1];
			});
			for(int i=0;i<(int)nR.size();i++){
				int idx=nR[i];
				if(V2[idxL][0]==P[idx][1]) V2[idxL][0]=V[V2[idxL][0]].nxt;
				if(V2[idxL][1]==P[idx][1]) V2[idxL][1]=V[V2[idxL][1]].prv;
				g[idx]=k;
				int L=V[P[idx][1]].prv,R=V[P[idx][1]].nxt;
				if(L) V[L].nxt=R;
				if(R) V[R].prv=L;
				V[P[idx][1]].prv=V[P[idx][1]].nxt=0;
				if(!V2[k][0]){
					V2[k][0]=V2[k][1]=P[idx][1];
				} else{
					V[V2[k][1]].nxt=P[idx][1];
					V[P[idx][1]].prv=V2[k][1];
					V2[k][1]=P[idx][1];
				}
				sz[idxL]--;
				sz[k]++;
			}
			R[k][0]=L+1;
			R[k][1]=yL;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
		if(sz[idxL]){
			R[idxL][0]=xL;
			R[idxL][1]=n-L;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
	}
}
void solve(int l,int r){
	if(l==r) return;
	int m=(l+r)>>1;
	solve(l,m);
	// [l, m]에서 추가된 점의 [m+1, r]에서의 쿼리 시 결과를 구한다.
	vector<pii> odrX,odrY;
	for(int i=l;i<=m;i++) if(arr[i][0]==0){
		int idx=arr[i][1];
		in[idx]=1;
		g[idx]=1;
		odrX.push_back({a[idx][0],idx});
		odrY.push_back({a[idx][1],idx});
	}
	sort(odrX.begin(),odrX.end());
	sort(odrY.begin(),odrY.end());
	for(auto [x,idx]: odrX){
		++t;
		P[idx][0]=t;
		V[t].val=idx;
		if(!V1[1][0]){
			V1[1][0]=V1[1][1]=t;
		} else{
			V[V1[1][1]].nxt=t;
			V[t].prv=V1[1][1];
			V1[1][1]=t;
		}
	}
	for(auto [y,idx]: odrY){
		++t;
		P[idx][1]=t;
		V[t].val=idx;
		if(!V2[1][0]){
			V2[1][0]=V2[1][1]=t;
		} else{
			V[V2[1][1]].nxt=t;
			V[t].prv=V2[1][1];
			V2[1][1]=t;
		}
		sz[1]++;
	}
	S1.insert({0,1});
	S2.insert({0,1});
	S1.insert({n+1,q+1557});
	S2.insert({n+1,q+1557});
	for(int i=m+1;i<=r;i++){
		if(arr[i][0]==2) SweepH(arr[i][1]);
		else if(arr[i][0]==3) SweepV(arr[i][1]);
		else if(arr[i][0]==1&&in[arr[i][1]]) ans[i]=Get(arr[i][1]);
	}
	for(int i=l;i<=m;i++) if(arr[i][0]==0){
		int idx=arr[i][1];
		a[idx]=Get(idx);
		in[idx]=0;
		g[idx]=0;
		P[idx]={0,0};
	}
	S1.clear();
	S2.clear();
	for(int i=1;i<=k;i++){
		R[i]={0,0};
		V1[i]=V2[i]={0,0};
		sz[i]=0;
	}
	for(int i=1;i<=t;i++){
		V[i].prv=V[i].nxt=0;
	}
	k=1;
	t=0;
	solve(m+1,r);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>a[i][0]>>a[i][1];
		arr[i]={0,i};
	}
	for(int op,i=1;i<=q;i++){
		cin>>op;
		if(op==1){
			int p;
			cin>>p;
			arr[i+m]={1,p};
		} else if(op==2){
			int l;
			cin>>l;
			arr[i+m]={2,l};
		} else if(op==3){
			int l;
			cin>>l;
			arr[i+m]={3,l};
		} else{
			m2++;
			cin>>a[m+m2][0]>>a[m+m2][1];
			arr[i+m]={0,m+m2};
		}
	}
	solve(1,m+q);
	for(int i=1;i<=m+q;i++) if(arr[i][0]==1){
		cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
	}
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25