| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047037 |
2024-08-07T07:57:27 Z |
이종영(#11084) |
Sweeping (JOI20_sweeping) |
C++17 |
|
2345 ms |
403560 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];
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(1){
R[idxL][0]=xL;
R[idxL][1]=L+1;
S1.insert({R[idxL][0],idxL});
S2.insert({R[idxL][1],idxL});
}
if(1){
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(1){
R[idxL][0]=n-L;
R[idxL][1]=yL;
S1.insert({R[idxL][0],idxL});
S2.insert({R[idxL][1],idxL});
}
if(1){
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];
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);
S1.insert({R[k][0],k});
S2.insert({R[k][1],k});
}
}
if(ok){
for(int idx: nR){
V1[idxL].insert({a[idx][0],idx});
V2[idxL].insert({a[idx][1],idx});
}
if(1){
R[idxL][0]=L+1;
R[idxL][1]=yL;
S1.insert({R[idxL][0],idxL});
S2.insert({R[idxL][1],idxL});
}
if(1){
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(1){
R[idxL][0]=xL;
R[idxL][1]=n-L;
S1.insert({R[idxL][0],idxL});
S2.insert({R[idxL][1],idxL});
}
if(1){
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(){
//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+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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
296528 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1497 ms |
403560 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2345 ms |
258292 KB |
Output is correct |
| 2 |
Correct |
1809 ms |
258388 KB |
Output is correct |
| 3 |
Incorrect |
771 ms |
257796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2345 ms |
258292 KB |
Output is correct |
| 2 |
Correct |
1809 ms |
258388 KB |
Output is correct |
| 3 |
Incorrect |
771 ms |
257796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
296528 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
