oj.uz

Submission #1047052

# Submission time Handle Problem Language Result Execution time Memory
1047052 2024-08-07T08:11:51 Z 이종영(#11084) Sweeping (JOI20_sweeping) C++17
64 / 100
 5188 ms 403596 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
const int N=1500005;
int n,m,q,k=1,g[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});
		}
	}
}
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];
		g[i]=1;
		V1[1].insert({a[i][0],i});
		V2[1].insert({a[i][1],i});
	}
	S1.insert({0,1});
	S2.insert({0,1});
	S1.insert({n+1,q+1557});
	S2.insert({n+1,q+1557});
	for(int op,t=1;t<=q;t++){
		cin>>op;
		if(op==1){
			int p;
			cin>>p;
			pii ans=Get(p);
			cout<<ans[0]<<" "<<ans[1]<<"\n";
			continue;
		} else if(op==2){
			int l;
			cin>>l;
			SweepH(l);
		} else if(op==3){
			int l;
			cin>>l;
			SweepV(l);
		} else{
			assert(0);
		}
	}
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 296700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1472 ms 403596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 212476 KB Output is correct
2 Correct 1131 ms 209220 KB Output is correct
3 Correct 955 ms 222792 KB Output is correct
4 Correct 981 ms 221780 KB Output is correct
5 Correct 1140 ms 209748 KB Output is correct
6 Correct 1024 ms 209196 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 212476 KB Output is correct
2 Correct 1131 ms 209220 KB Output is correct
3 Correct 955 ms 222792 KB Output is correct
4 Correct 981 ms 221780 KB Output is correct
5 Correct 1140 ms 209748 KB Output is correct
6 Correct 1024 ms 209196 KB Output is correct
7 Correct 4719 ms 228644 KB Output is correct
8 Correct 4690 ms 228544 KB Output is correct
9 Correct 4478 ms 228660 KB Output is correct
10 Correct 1572 ms 226356 KB Output is correct
11 Correct 1451 ms 221548 KB Output is correct
12 Correct 2565 ms 208888 KB Output is correct
13 Correct 2408 ms 208576 KB Output is correct
14 Correct 88 ms 146268 KB Output is correct
15 Correct 872 ms 208724 KB Output is correct
16 Correct 5188 ms 227280 KB Output is correct
17 Correct 4986 ms 226116 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 296700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -