oj.uz

Submission #1047063

# Submission time Handle Problem Language Result Execution time Memory
1047063 2024-08-07T08:25:45 Z 이종영(#11084) Sweeping (JOI20_sweeping) C++17
100 / 100
 15588 ms 273860 KB 
#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,g[N];
pii arr[N];
pii ans[N];
bool in[N];
pii a[N],R[N];
set<pii> V1[N],V2[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;
	while(V2[idxL].size()){
		{
			auto iter=V2[idxL].begin();
			int idx=(*iter)[1];
			if(Get(idx)[1]>L){
				ok=true;
				break;
			}
			V1[idxL].erase({a[idx][0],idx});
			V2[idxL].erase({a[idx][1],idx});
			nL.push_back(idx);
		}
		if(V2[idxL].empty()) break;
		{
			auto iter=prev(V2[idxL].end());
			int idx=(*iter)[1];
			if(Get(idx)[1]<=L) break;
			V1[idxL].erase({a[idx][0],idx});
			V2[idxL].erase({a[idx][1],idx});
			nR.push_back(idx);
		}
	}
	if(ok){
		for(int idx: nR){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		if(V1[idxL].size()){
			R[idxL][0]=xL;
			R[idxL][1]=L+1;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
		if(nL.size()){
			k++;
			for(int idx: nL){
				g[idx]=k;
				V1[k].insert({a[idx][0],idx});
				V2[k].insert({a[idx][1],idx});
			}
			R[k][0]=n-L;
			R[k][1]=yL;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
	} else{
		for(int idx: nL){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		if(V1[idxL].size()){
			R[idxL][0]=n-L;
			R[idxL][1]=yL;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
		if(nR.size()){
			k++;
			for(int idx: nR){
				g[idx]=k;
				V1[k].insert({a[idx][0],idx});
				V2[k].insert({a[idx][1],idx});
			}
			R[k][0]=xL;
			R[k][1]=L+1;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
	}
}
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;
	while(V1[idxL].size()){
		{
			auto iter=V1[idxL].begin();
			int idx=(*iter)[1];
			if(Get(idx)[0]>L){
				ok=true;
				break;
			}
			V1[idxL].erase({a[idx][0],idx});
			V2[idxL].erase({a[idx][1],idx});
			nL.push_back(idx);
		}
		if(V1[idxL].empty()) break;
		{
			auto iter=prev(V1[idxL].end());
			int idx=(*iter)[1];
			if(Get(idx)[0]<=L) break;
			V1[idxL].erase({a[idx][0],idx});
			V2[idxL].erase({a[idx][1],idx});
			nR.push_back(idx);
		}
	}
	if(ok){
		for(int idx: nR){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		if(V1[idxL].size()){
			R[idxL][0]=L+1;
			R[idxL][1]=yL;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
		if(nL.size()){
			k++;
			for(int idx: nL){
				g[idx]=k;
				V1[k].insert({a[idx][0],idx});
				V2[k].insert({a[idx][1],idx});
			}
			R[k][0]=xL;
			R[k][1]=n-L;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
	} else{
		for(int idx: nL){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		if(V1[idxL].size()){
			R[idxL][0]=xL;
			R[idxL][1]=n-L;
			S1.insert({R[idxL][0],idxL});
			S2.insert({R[idxL][1],idxL});
		}
		if(nR.size()){
			k++;
			for(int idx: nR){
				g[idx]=k;
				V1[k].insert({a[idx][0],idx});
				V2[k].insert({a[idx][1],idx});
			}
			R[k][0]=L+1;
			R[k][1]=yL;
			S1.insert({R[k][0],k});
			S2.insert({R[k][1],k});
		}
	}
}
void solve(int l,int r){
	if(l==r) return;
	int m=(l+r)>>1;
	solve(l,m);
	// [l, m]에서 추가된 점의 [m+1, r]에서의 쿼리 시 결과를 구한다.
	for(int i=l;i<=m;i++) if(arr[i][0]==0){
		int idx=arr[i][1];
		in[idx]=1;
		g[idx]=1;
		V1[1].insert({a[idx][0],idx});
		V2[1].insert({a[idx][1],idx});
	}
	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;
	}
	S1.clear();
	S2.clear();
	for(int i=1;i<=k;i++){
		V1[i].clear();
		V2[i].clear();
		R[i]={0,0};
	}
	k=1;
	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 33 ms 150616 KB Output is correct
2 Correct 26 ms 150284 KB Output is correct
3 Correct 24 ms 150620 KB Output is correct
4 Correct 30 ms 150616 KB Output is correct
5 Correct 48 ms 150672 KB Output is correct
6 Correct 22 ms 150620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13289 ms 248744 KB Output is correct
2 Correct 13229 ms 259200 KB Output is correct
3 Correct 13109 ms 248756 KB Output is correct
4 Correct 5041 ms 241528 KB Output is correct
5 Correct 5460 ms 241328 KB Output is correct
6 Correct 11739 ms 253692 KB Output is correct
7 Correct 11889 ms 244148 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3922 ms 250616 KB Output is correct
2 Correct 3307 ms 253488 KB Output is correct
3 Correct 2649 ms 257028 KB Output is correct
4 Correct 2295 ms 265064 KB Output is correct
5 Correct 3255 ms 253540 KB Output is correct
6 Correct 2813 ms 252624 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3922 ms 250616 KB Output is correct
2 Correct 3307 ms 253488 KB Output is correct
3 Correct 2649 ms 257028 KB Output is correct
4 Correct 2295 ms 265064 KB Output is correct
5 Correct 3255 ms 253540 KB Output is correct
6 Correct 2813 ms 252624 KB Output is correct
7 Correct 9309 ms 270972 KB Output is correct
8 Correct 9353 ms 251184 KB Output is correct
9 Correct 9295 ms 251404 KB Output is correct
10 Correct 4673 ms 243868 KB Output is correct
11 Correct 3968 ms 245460 KB Output is correct
12 Correct 5183 ms 232592 KB Output is correct
13 Correct 5022 ms 232996 KB Output is correct
14 Correct 410 ms 160596 KB Output is correct
15 Correct 2848 ms 233336 KB Output is correct
16 Correct 8568 ms 249676 KB Output is correct
17 Correct 8584 ms 242028 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 150616 KB Output is correct
2 Correct 26 ms 150284 KB Output is correct
3 Correct 24 ms 150620 KB Output is correct
4 Correct 30 ms 150616 KB Output is correct
5 Correct 48 ms 150672 KB Output is correct
6 Correct 22 ms 150620 KB Output is correct
7 Correct 13289 ms 248744 KB Output is correct
8 Correct 13229 ms 259200 KB Output is correct
9 Correct 13109 ms 248756 KB Output is correct
10 Correct 5041 ms 241528 KB Output is correct
11 Correct 5460 ms 241328 KB Output is correct
12 Correct 11739 ms 253692 KB Output is correct
13 Correct 11889 ms 244148 KB Output is correct
14 Correct 3922 ms 250616 KB Output is correct
15 Correct 3307 ms 253488 KB Output is correct
16 Correct 2649 ms 257028 KB Output is correct
17 Correct 2295 ms 265064 KB Output is correct
18 Correct 3255 ms 253540 KB Output is correct
19 Correct 2813 ms 252624 KB Output is correct
20 Correct 9309 ms 270972 KB Output is correct
21 Correct 9353 ms 251184 KB Output is correct
22 Correct 9295 ms 251404 KB Output is correct
23 Correct 4673 ms 243868 KB Output is correct
24 Correct 3968 ms 245460 KB Output is correct
25 Correct 5183 ms 232592 KB Output is correct
26 Correct 5022 ms 232996 KB Output is correct
27 Correct 410 ms 160596 KB Output is correct
28 Correct 2848 ms 233336 KB Output is correct
29 Correct 8568 ms 249676 KB Output is correct
30 Correct 8584 ms 242028 KB Output is correct
31 Correct 8683 ms 249656 KB Output is correct
32 Correct 11158 ms 264488 KB Output is correct
33 Correct 10853 ms 269380 KB Output is correct
34 Correct 15586 ms 273684 KB Output is correct
35 Correct 15588 ms 273860 KB Output is correct
36 Correct 5134 ms 253656 KB Output is correct
37 Correct 5476 ms 268828 KB Output is correct
38 Correct 6627 ms 256948 KB Output is correct
39 Correct 6734 ms 256536 KB Output is correct
40 Correct 10372 ms 260988 KB Output is correct