oj.uz

답안 #1047021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047021 2024-08-07T07:42:34 Z 이종영(#11084) 청소 (JOI20_sweeping) C++17
0 / 100
 2841 ms 403648 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+1});
	int idxL=(*prev(iter))[1];
	int xL=R[idxL][0],yL=R[idxL][1];
	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});
		}
		R[idxL][0]=xL;
		R[idxL][1]=L+1;
		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;
		}
	} else{
		for(int idx: nL){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		R[idxL][0]=n-L;
		R[idxL][1]=yL;
		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[idxL][0],idxL});
	S2.insert({R[idxL][1],idxL});
	S1.insert({R[k][0],k});
	S2.insert({R[k][1],k});
}
void SweepV(int L){
	auto iter=S1.upper_bound({L,q+1});
	int idxL=(*prev(iter))[1];
	int xL=R[idxL][0],yL=R[idxL][1];
	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});
		}
		R[idxL][0]=L+1;
		R[idxL][1]=yL;
		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;
		}
	} else{
		for(int idx: nL){
			V1[idxL].insert({a[idx][0],idx});
			V2[idxL].insert({a[idx][1],idx});
		}
		R[idxL][0]=xL;
		R[idxL][1]=n-L;
		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[idxL][0],idxL});
	S2.insert({R[idxL][1],idxL});
	S1.insert({R[k][0],k});
	S2.insert({R[k][1],k});
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	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+1});
	S2.insert({n+1,q+1});
	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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 106 ms 296740 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1476 ms 403648 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2841 ms 222548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2841 ms 222548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 106 ms 296740 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -