#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
set<int> st[4324242];
void update(int id, int l, int r, int pos, int v)
{
if(pos>=r||pos<l) return ;
st[id].insert(v);
if(r-l<2) return ;
int mid=(l+r)>>1;
update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
}
const int INF = int(1e9)+11;
int query(int id, int l, int r, int ql, int qr, int y)
{
if(ql>=r||l>=qr) return INF;
if(ql<=l&&r<=qr)
{
auto it = st[id].lower_bound(y);
if(it==st[id].end()) return INF;
return (*it);
}
int mid=(l+r)>>1;
return min(query(id*2,l,mid,ql,qr,y),query(id*2+1,mid,r,ql,qr,y));
}
struct node
{
int lazy;
int mn;
};
node stx[2222222];
node sty[2222222];
vector<ii> pt;
void combine(int id)
{
stx[id].mn=min(stx[id*2].mn,stx[id*2+1].mn);
sty[id].mn=min(sty[id*2].mn,sty[id*2+1].mn);
}
void build(int id, int l, int r)
{
stx[id].lazy=sty[id].lazy=-1;
if(r-l<2)
{
stx[id].mn=pt[l].fi;
sty[id].mn=pt[l].se;
return ;
}
int mid=(l+r)>>1;
build(id*2,l,mid); build(id*2+1,mid,r);
combine(id);
}
void pushx(int id, int l, int r)
{
if(stx[id].lazy!=-1)
{
stx[id].mn=stx[id].lazy;
if(r-l>=2)
{
stx[id*2].lazy=stx[id*2+1].lazy=stx[id].lazy;
}
stx[id].lazy=-1;
}
}
void pushy(int id, int l, int r)
{
if(sty[id].lazy!=-1)
{
sty[id].mn=sty[id].lazy;
if(r-l>=2)
{
sty[id*2].lazy=sty[id*2+1].lazy=sty[id].lazy;
}
sty[id].lazy=-1;
}
}
void updatex(int id, int l, int r, int ql, int qr, int v)
{
pushx(id,l,r); pushy(id,l,r);
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
stx[id].lazy=v;
pushx(id,l,r);
return ;
}
int mid=(l+r)>>1;
updatex(id*2,l,mid,ql,qr,v); updatex(id*2+1,mid,r,ql,qr,v);
combine(id);
}
void updatey(int id, int l, int r, int ql, int qr, int v)
{
pushy(id,l,r); pushx(id,l,r);
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
sty[id].lazy=v;
pushy(id,l,r);
return ;
}
int mid=(l+r)>>1;
updatey(id*2,l,mid,ql,qr,v); updatey(id*2+1,mid,r,ql,qr,v);
combine(id);
}
ii query(int id, int l, int r, int pos)
{
pushx(id,l,r); pushy(id,l,r);
if(pos>=r||pos<l) return {-1,-1};
if(r-l<2)
{
return {stx[id].mn,sty[id].mn};
}
int mid=(l+r)>>1;
return max(query(id*2,l,mid,pos),query(id*2+1,mid,r,pos));
}
int getrightmostx(int id, int l, int r, int v) //rightmost x that is <= v
{
pushx(id,l,r); pushy(id,l,r);
if(stx[id].mn>v) return -1;
if(r-l<2) return l;
int mid=(l+r)>>1;
if(stx[id*2+1].mn<=v) return getrightmostx(id*2+1,mid,r,v);
else return getrightmostx(id*2,l,mid,v);
}
int getleftmosty(int id, int l, int r, int v) //leftmost x that is <= v
{
pushx(id,l,r); pushy(id,l,r);
if(sty[id].mn>v) return INF;
if(r-l<2) return l;
int mid=(l+r)>>1;
if(sty[id*2].mn<=v) return getleftmosty(id*2,l,mid,v);
else return getleftmosty(id*2+1,mid,r,v);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,m,q; cin>>n>>m>>q;
vi T;
for(int i=0;i<m;i++)
{
int x,y; cin>>x>>y;
pt.pb({x,y}); T.pb(0);
}
int sub3=1;
for(int i=1;i<m;i++)
{
if(pt[i].fi<pt[i-1].fi||pt[i].se>pt[i-1].se) {sub3=0; break;}
}
if(sub3)
{
build(1,0,m);
for(int z=0;z<q;z++)
{
int t; cin>>t;
if(t==1)
{
int id; cin>>id; id--;
ii tmp = query(1,0,m,id);
cout<<tmp.fi<<' '<<tmp.se<<'\n';
}
else if(t==2)
{
int l; cin>>l;
int R = getrightmostx(1,0,m,n-l);
int L = getleftmosty(1,0,m,l);
if(L<=R)
{
updatex(1,0,m,L,R+1,n-l);
}
}
else
{
int l; cin>>l;
int R = getrightmostx(1,0,m,l);
int L = getleftmosty(1,0,m,n-l);
if(L<=R)
{
updatey(1,0,m,L,R+1,n-l);
}
}
}
return 0;
}
if(m<=2000&&q<=5000)
{
for(int z=0;z<q;z++)
{
int t; cin>>t;
if(t==4)
{
int x,y; cin>>x>>y;
pt.pb({x,y});
}
else if(t==3)
{
int L; cin>>L;
for(int i=0;i<pt.size();i++)
{
if(L>=pt[i].fi) pt[i].se=max(pt[i].se,n-L);
}
}
else if(t==2)
{
int L; cin>>L;
for(int i=0;i<pt.size();i++)
{
if(L>=pt[i].se) pt[i].fi=max(pt[i].fi,n-L);
}
}
else
{
int id; cin>>id; id--;
cout<<pt[id].fi<<' '<<pt[id].se<<'\n';
}
}
}
else
{
vector<pair<ii,int> > queries;
for(int z=0;z<q;z++)
{
int t; cin>>t;
if(t==4)
{
int x,y; cin>>x>>y;
pt.pb({x,y});
T.pb(z);
}
else if(t==2)
{
int L; cin>>L;
update(1,0,q,z,L);
}
else
{
int id; cin>>id; id--;
int y = pt[id].se;
int ans = query(1,0,q,T[id],q,y);
int x = pt[id].fi;
if(ans<INF) x = max(x, n-ans);
cout<<x<<' '<<y<<'\n';
}
}
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:227:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<pt.size();i++)
~^~~~~~~~~~
sweeping.cpp:235:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<pt.size();i++)
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
203640 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
203512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5585 ms |
619132 KB |
Output is correct |
| 2 |
Correct |
5440 ms |
616184 KB |
Output is correct |
| 3 |
Correct |
5247 ms |
615980 KB |
Output is correct |
| 4 |
Correct |
3479 ms |
615380 KB |
Output is correct |
| 5 |
Correct |
3417 ms |
615284 KB |
Output is correct |
| 6 |
Correct |
5558 ms |
615576 KB |
Output is correct |
| 7 |
Correct |
5777 ms |
615716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1069 ms |
239308 KB |
Output is correct |
| 2 |
Correct |
969 ms |
239296 KB |
Output is correct |
| 3 |
Correct |
918 ms |
238688 KB |
Output is correct |
| 4 |
Correct |
1135 ms |
239200 KB |
Output is correct |
| 5 |
Correct |
955 ms |
239076 KB |
Output is correct |
| 6 |
Correct |
959 ms |
239200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1069 ms |
239308 KB |
Output is correct |
| 2 |
Correct |
969 ms |
239296 KB |
Output is correct |
| 3 |
Correct |
918 ms |
238688 KB |
Output is correct |
| 4 |
Correct |
1135 ms |
239200 KB |
Output is correct |
| 5 |
Correct |
955 ms |
239076 KB |
Output is correct |
| 6 |
Correct |
959 ms |
239200 KB |
Output is correct |
| 7 |
Runtime error |
471 ms |
429408 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
203640 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
203512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
