oj.uz

Submission #1047924

# Submission time Handle Problem Language Result Execution time Memory
1047924 2024-08-07T17:39:59 Z moonrabbit2 Sweeping (JOI20_sweeping) C++17
100 / 100
 4022 ms 119524 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14936 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 7 ms 14940 KB Output is correct
5 Correct 10 ms 14940 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3293 ms 108284 KB Output is correct
2 Correct 3431 ms 106416 KB Output is correct
3 Correct 3300 ms 107484 KB Output is correct
4 Correct 1916 ms 100048 KB Output is correct
5 Correct 1896 ms 100628 KB Output is correct
6 Correct 2283 ms 95568 KB Output is correct
7 Correct 3242 ms 101344 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 88152 KB Output is correct
2 Correct 953 ms 72632 KB Output is correct
3 Correct 1062 ms 79296 KB Output is correct
4 Correct 1085 ms 88008 KB Output is correct
5 Correct 991 ms 73156 KB Output is correct
6 Correct 925 ms 65556 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 88152 KB Output is correct
2 Correct 953 ms 72632 KB Output is correct
3 Correct 1062 ms 79296 KB Output is correct
4 Correct 1085 ms 88008 KB Output is correct
5 Correct 991 ms 73156 KB Output is correct
6 Correct 925 ms 65556 KB Output is correct
7 Correct 2135 ms 95924 KB Output is correct
8 Correct 2163 ms 94308 KB Output is correct
9 Correct 2105 ms 94480 KB Output is correct
10 Correct 1587 ms 84636 KB Output is correct
11 Correct 1409 ms 87484 KB Output is correct
12 Correct 1359 ms 65184 KB Output is correct
13 Correct 1421 ms 64164 KB Output is correct
14 Correct 415 ms 20816 KB Output is correct
15 Correct 1054 ms 64840 KB Output is correct
16 Correct 2114 ms 91516 KB Output is correct
17 Correct 2177 ms 74908 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14936 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 7 ms 14940 KB Output is correct
5 Correct 10 ms 14940 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct
7 Correct 3293 ms 108284 KB Output is correct
8 Correct 3431 ms 106416 KB Output is correct
9 Correct 3300 ms 107484 KB Output is correct
10 Correct 1916 ms 100048 KB Output is correct
11 Correct 1896 ms 100628 KB Output is correct
12 Correct 2283 ms 95568 KB Output is correct
13 Correct 3242 ms 101344 KB Output is correct
14 Correct 1109 ms 88152 KB Output is correct
15 Correct 953 ms 72632 KB Output is correct
16 Correct 1062 ms 79296 KB Output is correct
17 Correct 1085 ms 88008 KB Output is correct
18 Correct 991 ms 73156 KB Output is correct
19 Correct 925 ms 65556 KB Output is correct
20 Correct 2135 ms 95924 KB Output is correct
21 Correct 2163 ms 94308 KB Output is correct
22 Correct 2105 ms 94480 KB Output is correct
23 Correct 1587 ms 84636 KB Output is correct
24 Correct 1409 ms 87484 KB Output is correct
25 Correct 1359 ms 65184 KB Output is correct
26 Correct 1421 ms 64164 KB Output is correct
27 Correct 415 ms 20816 KB Output is correct
28 Correct 1054 ms 64840 KB Output is correct
29 Correct 2114 ms 91516 KB Output is correct
30 Correct 2177 ms 74908 KB Output is correct
31 Correct 2003 ms 97916 KB Output is correct
32 Correct 3108 ms 111600 KB Output is correct
33 Correct 3105 ms 119524 KB Output is correct
34 Correct 4022 ms 118532 KB Output is correct
35 Correct 3993 ms 113036 KB Output is correct
36 Correct 1887 ms 99656 KB Output is correct
37 Correct 2062 ms 106856 KB Output is correct
38 Correct 2242 ms 94824 KB Output is correct
39 Correct 2165 ms 96812 KB Output is correct
40 Correct 2970 ms 102816 KB Output is correct