| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260923 |
2020-08-11T08:05:00 Z |
최은수(#5044) |
Sweeping (JOI20_sweeping) |
C++17 |
|
7572 ms |
302340 KB |
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
pi pos[500010];
int gr[500010];
int xmn[1000010],ymn[1000010];
int gct;
struct cmp1
{
inline bool operator()(const int&x,const int&y)const
{
return pi(pos[x].fi,x)<pi(pos[y].fi,y);
}
};
struct cmp2
{
inline bool operator()(const int&x,const int&y)const
{
return pi(pos[x].se,x)<pi(pos[y].se,y);
}
};
set<int,cmp1>stx[1000010];
set<int,cmp2>sty[1000010];
set<pi>st;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,q;
cin>>n>>m>>q;
st.ep(0,0);
for(int i=0;i++<m;)
{
cin>>pos[i].fi>>pos[i].se;
stx[0].ep(i);
sty[0].ep(i);
}
for(int i=0;i<q;i++)
{
int t,l;
cin>>t>>l;
if(t==1)
{
cout<<max(pos[l].fi,xmn[gr[l]])<<' '<<max(pos[l].se,ymn[gr[l]])<<'\n';
}
else if(t==2)
{
int g=(--st.upper_bound(pi(n-l,inf)))->se;
if(stx[g].empty()||xmn[g]==n-l)
continue;
vector<int>nx1,nx2;
auto it1=sty[g].begin(),it2=sty[g].end();
int par=0,sml=1;
while(it1!=it2)
{
if(par==0)
{
if(pos[*it1].se>l)
{
sml=0;
break;
}
nx1.eb(*it1);
it1++;
}
else
{
it2--;
if(pos[*it2].se<=l)
{
sml=1;
break;
}
nx2.eb(*it2);
}
par^=1;
}
gct++;
if(sml==0)
{
xmn[gct]=n-l;
ymn[gct]=ymn[g];
ymn[g]=l+1;
st.ep(xmn[gct],gct);
for(int&t:nx1)
{
gr[t]=gct;
stx[gct].ep(t);
sty[gct].ep(t);
stx[g].erase(t);
sty[g].erase(t);
}
}
else
{
st.erase(pi(xmn[g],g));
xmn[gct]=xmn[g];
ymn[gct]=l+1;
xmn[g]=n-l;
st.ep(xmn[gct],gct);
st.ep(xmn[g],g);
for(int&t:nx2)
{
gr[t]=gct;
stx[gct].ep(t);
sty[gct].ep(t);
stx[g].erase(t);
sty[g].erase(t);
}
}
}
else if(t==3)
{
int g=(--st.upper_bound(pi(l+1,inf)))->se;
if(stx[g].empty()||xmn[g]==l+1)
continue;
vector<int>nx1,nx2;
auto it1=stx[g].begin(),it2=stx[g].end();
int par=0,sml=1;
while(it1!=it2)
{
if(par==0)
{
if(pos[*it1].fi>l)
{
sml=0;
break;
}
nx1.eb(*it1);
it1++;
}
else
{
it2--;
if(pos[*it2].fi<=l)
{
sml=1;
break;
}
nx2.eb(*it2);
}
par^=1;
}
gct++;
if(sml==0)
{
st.erase(pi(xmn[g],g));
xmn[gct]=xmn[g];
ymn[gct]=n-l;
xmn[g]=l+1;
st.ep(xmn[gct],gct);
st.ep(xmn[g],g);
for(int&t:nx1)
{
gr[t]=gct;
stx[gct].ep(t);
sty[gct].ep(t);
stx[g].erase(t);
sty[g].erase(t);
}
}
else
{
xmn[gct]=l+1;
ymn[gct]=ymn[g];
ymn[g]=n-l;
st.ep(xmn[gct],gct);
for(int&t:nx2)
{
gr[t]=gct;
stx[gct].ep(t);
sty[gct].ep(t);
stx[g].erase(t);
sty[g].erase(t);
}
}
}
else
{
}
}
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
94584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4462 ms |
302340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2460 ms |
165384 KB |
Output is correct |
| 2 |
Correct |
1790 ms |
158928 KB |
Output is correct |
| 3 |
Correct |
1387 ms |
170324 KB |
Output is correct |
| 4 |
Correct |
1434 ms |
182188 KB |
Output is correct |
| 5 |
Correct |
1883 ms |
160324 KB |
Output is correct |
| 6 |
Correct |
1738 ms |
158972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2460 ms |
165384 KB |
Output is correct |
| 2 |
Correct |
1790 ms |
158928 KB |
Output is correct |
| 3 |
Correct |
1387 ms |
170324 KB |
Output is correct |
| 4 |
Correct |
1434 ms |
182188 KB |
Output is correct |
| 5 |
Correct |
1883 ms |
160324 KB |
Output is correct |
| 6 |
Correct |
1738 ms |
158972 KB |
Output is correct |
| 7 |
Correct |
7572 ms |
179556 KB |
Output is correct |
| 8 |
Correct |
7228 ms |
179496 KB |
Output is correct |
| 9 |
Correct |
7034 ms |
179552 KB |
Output is correct |
| 10 |
Correct |
3498 ms |
179704 KB |
Output is correct |
| 11 |
Correct |
3015 ms |
182880 KB |
Output is correct |
| 12 |
Correct |
4730 ms |
159512 KB |
Output is correct |
| 13 |
Correct |
4778 ms |
161252 KB |
Output is correct |
| 14 |
Correct |
223 ms |
97144 KB |
Output is correct |
| 15 |
Correct |
2125 ms |
160232 KB |
Output is correct |
| 16 |
Correct |
7445 ms |
179936 KB |
Output is correct |
| 17 |
Correct |
6733 ms |
179088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
94584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
