#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct Splay
{
int p, l, r, c, x, y, yl;
Splay() : p(0), l(0), r(0), c(1), x(0), y(0), yl(-1) {}
} tree[1500001];
const int SZ=1<<21;
vector<pair<int,int>> Q;
vector<int> x;
int mtree[2*SZ], lz[2*SZ], R[1500000];
void lazy(int c)
{
if(tree[c].l) tree[tree[c].l].x=tree[c].x;
if(tree[c].r) tree[tree[c].r].x=tree[c].x;
tree[c].y=max(tree[c].y,tree[c].yl);
if(tree[c].l) tree[tree[c].l].yl=max(tree[tree[c].l].yl,tree[c].yl);
if(tree[c].r) tree[tree[c].r].yl=max(tree[tree[c].r].yl,tree[c].yl);
tree[c].yl=-1;
}
void update(int c) {tree[c].c=tree[tree[c].l].c+tree[tree[c].r].c+1;}
void rotate(int c)
{
int p=tree[c].p;
if(tree[p].l==c) {
if(tree[c].r) tree[tree[c].r].p=p;
tree[p].l=tree[c].r;
tree[c].r=p;
}
else {
if(tree[c].l) tree[tree[c].l].p=p;
tree[p].r=tree[c].l;
tree[c].l=p;
}
if(tree[p].p) (tree[tree[p].p].l==p ? tree[tree[p].p].l:tree[tree[p].p].r)=c;
tree[c].p=tree[p].p;
tree[p].p=c;
update(p); update(c);
}
void splay(int c)
{
while(tree[c].p) {
int p=tree[c].p;
if(tree[p].p) lazy(tree[p].p);
lazy(p); lazy(c);
if(tree[p].p) rotate((tree[tree[p].p].l==p)==(tree[p].l==c) ? p:c);
rotate(c);
}
lazy(c);
}
int add_node(int c, int v)
{
splay(c);
for(;;) {
lazy(c);
if(tree[c].y<tree[v].y) {
if(tree[c].r==0) {
splay(c);
if(tree[v].r=tree[c].r) tree[tree[v].r].p=v;
tree[c].r=v;
tree[v].p=c;
update(v); update(c);
return c;
}
c=tree[c].r;
}
else {
if(tree[c].l==0) {
splay(c);
if(tree[v].l=tree[c].l) tree[tree[v].l].p=v;
tree[c].l=v;
tree[v].p=c;
update(v); update(c);
return c;
}
c=tree[c].l;
}
}
}
void lazy_propagation(int bit, int s, int e)
{
mtree[bit]=max(mtree[bit],lz[bit]);
if(s<e) {
if(mtree[2*bit]<0x7f7f7f7f) lz[2*bit]=max(lz[2*bit],lz[bit]);
if(mtree[2*bit+1]<0x7f7f7f7f) lz[2*bit+1]=max(lz[2*bit+1],lz[bit]);
}
else if(R[s]>-1) {
tree[R[s]].yl=max(tree[R[s]].yl,lz[bit]);
lazy(R[s]);
}
lz[bit]=-1;
}
void push(int n)
{
int bit=1, s=0, e=SZ-1;
while(s<e) {
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n<=m) tie(bit,e)=make_pair(2*bit,m);
else tie(bit,s)=make_pair(2*bit+1,m+1);
}
lazy_propagation(bit,s,e);
}
void dfs(int &c, int p)
{
int l=tree[p].l, r=tree[p].r;
lazy(p); tree[p].p=tree[p].l=tree[p].r=0;
if(l) dfs(c,l);
c=add_node(c,p);
if(r) dfs(c,r);
}
void query(int n1, int n2, int p, int v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1 || mtree[bit]>v) return;
if(s==e) {
int &c=R[m];
for(;;) {
lazy(c);
if(tree[c].y>v) {
if(tree[c].l==0) {
splay(c);
break;
}
c=tree[c].l;
}
else {
if(tree[c].r==0) {
splay(c);
if(tree[c].r) {
for(lazy(c=tree[c].r);tree[c].l;) lazy(c=tree[c].l);
splay(c);
}
break;
}
c=tree[c].r;
}
}
mtree[SZ+p]=min(mtree[SZ+p],mtree[bit]);
if(tree[c].y<=v) {
mtree[bit]=0x7f7f7f7f;
if(R[p]==-1) {
swap(c,R[p]);
tree[R[p]].x=x[p];
lazy(R[p]);
return;
}
if(tree[c].c>tree[R[p]].c) swap(c,R[p]);
dfs(R[p],c); c=-1; tree[R[p]].x=x[p]; lazy(R[p]);
}
else {
mtree[bit]=tree[c].y;
tree[v=tree[c].l].p=0;
tree[c].l=0; update(c);
if(R[p]==-1) {
R[p]=v;
tree[R[p]].x=x[p]; lazy(R[p]);
return;
}
if(tree[v].c>tree[R[p]].c) swap(v,R[p]);
dfs(R[p],v); tree[R[p]].x=x[p]; lazy(R[p]);
}
return;
}
query(n1,n2,p,v,2*bit,s,m);
query(n1,n2,p,v,2*bit+1,m+1,e);
mtree[bit]=min(mtree[2*bit],mtree[2*bit+1]);
}
void set_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1) return;
if(n1<=s && e<=n2) {
lz[bit]=v;
lazy_propagation(bit,s,e);
return;
}
set_tree(n1,n2,v,2*bit,s,m);
set_tree(n1,n2,v,2*bit+1,m+1,e);
mtree[bit]=min(mtree[2*bit],mtree[2*bit+1]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int L, N, B, M;
cin>>L>>N>>M; tree[0].c=0;
memset(lz,-1,sizeof(lz));
memset(R,-1,sizeof(R));
memset(mtree,0x7f,sizeof(mtree));
for(int i=1;i<=N;i++) {
int a, b;
cin>>a>>b;
x.push_back(a);
tree[i].x=a;
tree[i].y=b;
}
Q.resize(M); B=N;
for(auto &[t,a]: Q) {
cin>>t>>a;
if(t==2) x.push_back(L-a);
else if(t==4) {
int b;
cin>>b;
x.push_back(a);
tree[++N].x=a;
tree[a=N].y=b;
}
}
sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
for(int i=1;i<=B;i++) {
int p=lower_bound(x.begin(),x.end(),tree[i].x)-x.begin();
if(R[p]==-1) R[p]=i;
else R[p]=add_node(R[p],i);
mtree[SZ+p]=min(mtree[SZ+p],tree[i].y);
}
for(int i=SZ;--i;) mtree[i]=min(mtree[2*i],mtree[2*i+1]);
for(auto[t,a]: Q) {
int p;
if(t==1) {
splay(a);
R[p=lower_bound(x.begin(),x.end(),tree[a].x)-x.begin()]=a;
push(p);
cout<<tree[a].x<<' '<<tree[a].y<<'\n';
}
else if(t==2) {
p=lower_bound(x.begin(),x.end(),L-a)-x.begin();
push(p); query(0,p-1,p,a);
for(p+=SZ;p>>=1;) mtree[p]=min(max(mtree[2*p],lz[2*p]),max(mtree[2*p+1],lz[2*p+1]));
}
else if(t==3) {
p=upper_bound(x.begin(),x.end(),a)-x.begin()-1;
set_tree(0,p,L-a);
}
else {
p=lower_bound(x.begin(),x.end(),tree[a].x)-x.begin();
push(p);
if(R[p]==-1) R[p]=a;
else R[p]=add_node(R[p],a);
p+=SZ;
for(mtree[p]=min(mtree[p],tree[a].y);p>>=1;) mtree[p]=min(max(mtree[2*p],lz[2*p]),max(mtree[2*p+1],lz[2*p+1]));
}
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int add_node(int, int)':
sweeping.cpp:75:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
75 | if(tree[v].r=tree[c].r) tree[tree[v].r].p=v;
| ~~~~~~~~~^~~~~~~~~~
sweeping.cpp:86:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
86 | if(tree[v].l=tree[c].l) tree[tree[v].l].p=v;
| ~~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
80320 KB |
Output is correct |
2 |
Correct |
52 ms |
80172 KB |
Output is correct |
3 |
Correct |
50 ms |
80176 KB |
Output is correct |
4 |
Correct |
54 ms |
80316 KB |
Output is correct |
5 |
Correct |
55 ms |
80200 KB |
Output is correct |
6 |
Correct |
52 ms |
80128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3115 ms |
122800 KB |
Output is correct |
2 |
Correct |
3042 ms |
122808 KB |
Output is correct |
3 |
Correct |
3073 ms |
122712 KB |
Output is correct |
4 |
Correct |
2508 ms |
121668 KB |
Output is correct |
5 |
Correct |
4038 ms |
122204 KB |
Output is correct |
6 |
Correct |
3857 ms |
122356 KB |
Output is correct |
7 |
Correct |
3093 ms |
122912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2351 ms |
121348 KB |
Output is correct |
2 |
Correct |
2382 ms |
120772 KB |
Output is correct |
3 |
Correct |
1472 ms |
119640 KB |
Output is correct |
4 |
Correct |
1800 ms |
120528 KB |
Output is correct |
5 |
Correct |
2112 ms |
119904 KB |
Output is correct |
6 |
Correct |
2332 ms |
120704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2351 ms |
121348 KB |
Output is correct |
2 |
Correct |
2382 ms |
120772 KB |
Output is correct |
3 |
Correct |
1472 ms |
119640 KB |
Output is correct |
4 |
Correct |
1800 ms |
120528 KB |
Output is correct |
5 |
Correct |
2112 ms |
119904 KB |
Output is correct |
6 |
Correct |
2332 ms |
120704 KB |
Output is correct |
7 |
Correct |
2677 ms |
120720 KB |
Output is correct |
8 |
Correct |
2730 ms |
120696 KB |
Output is correct |
9 |
Correct |
2649 ms |
120752 KB |
Output is correct |
10 |
Correct |
2013 ms |
119728 KB |
Output is correct |
11 |
Correct |
2860 ms |
120544 KB |
Output is correct |
12 |
Correct |
3575 ms |
120776 KB |
Output is correct |
13 |
Correct |
3872 ms |
120756 KB |
Output is correct |
14 |
Correct |
1020 ms |
93868 KB |
Output is correct |
15 |
Correct |
1753 ms |
115804 KB |
Output is correct |
16 |
Correct |
2772 ms |
121312 KB |
Output is correct |
17 |
Correct |
2549 ms |
120768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
80320 KB |
Output is correct |
2 |
Correct |
52 ms |
80172 KB |
Output is correct |
3 |
Correct |
50 ms |
80176 KB |
Output is correct |
4 |
Correct |
54 ms |
80316 KB |
Output is correct |
5 |
Correct |
55 ms |
80200 KB |
Output is correct |
6 |
Correct |
52 ms |
80128 KB |
Output is correct |
7 |
Correct |
3115 ms |
122800 KB |
Output is correct |
8 |
Correct |
3042 ms |
122808 KB |
Output is correct |
9 |
Correct |
3073 ms |
122712 KB |
Output is correct |
10 |
Correct |
2508 ms |
121668 KB |
Output is correct |
11 |
Correct |
4038 ms |
122204 KB |
Output is correct |
12 |
Correct |
3857 ms |
122356 KB |
Output is correct |
13 |
Correct |
3093 ms |
122912 KB |
Output is correct |
14 |
Correct |
2351 ms |
121348 KB |
Output is correct |
15 |
Correct |
2382 ms |
120772 KB |
Output is correct |
16 |
Correct |
1472 ms |
119640 KB |
Output is correct |
17 |
Correct |
1800 ms |
120528 KB |
Output is correct |
18 |
Correct |
2112 ms |
119904 KB |
Output is correct |
19 |
Correct |
2332 ms |
120704 KB |
Output is correct |
20 |
Correct |
2677 ms |
120720 KB |
Output is correct |
21 |
Correct |
2730 ms |
120696 KB |
Output is correct |
22 |
Correct |
2649 ms |
120752 KB |
Output is correct |
23 |
Correct |
2013 ms |
119728 KB |
Output is correct |
24 |
Correct |
2860 ms |
120544 KB |
Output is correct |
25 |
Correct |
3575 ms |
120776 KB |
Output is correct |
26 |
Correct |
3872 ms |
120756 KB |
Output is correct |
27 |
Correct |
1020 ms |
93868 KB |
Output is correct |
28 |
Correct |
1753 ms |
115804 KB |
Output is correct |
29 |
Correct |
2772 ms |
121312 KB |
Output is correct |
30 |
Correct |
2549 ms |
120768 KB |
Output is correct |
31 |
Correct |
2421 ms |
121840 KB |
Output is correct |
32 |
Correct |
2500 ms |
121432 KB |
Output is correct |
33 |
Correct |
1997 ms |
122236 KB |
Output is correct |
34 |
Correct |
2979 ms |
121180 KB |
Output is correct |
35 |
Correct |
3066 ms |
121272 KB |
Output is correct |
36 |
Correct |
2108 ms |
120980 KB |
Output is correct |
37 |
Correct |
3259 ms |
121324 KB |
Output is correct |
38 |
Correct |
4037 ms |
122180 KB |
Output is correct |
39 |
Correct |
4097 ms |
121608 KB |
Output is correct |
40 |
Correct |
2689 ms |
121920 KB |
Output is correct |