#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1.5e6;
struct Point
{
int x, y, p;
};
struct Query
{
int t, p, x, y;
};
int N, M, Q;
Point A[MAXN+10];
Query B[MAXN+10];
int pos[MAXN+10];
struct SEG
{
vector<int> tree, lazy;
SEG()
{
tree.resize(MAXN*4+10);
lazy.resize(MAXN*4+10);
}
void busy(int node, int tl, int tr)
{
tree[node]=max(tree[node], lazy[node]);
if(tl!=tr)
{
lazy[node*2]=max(lazy[node*2], lazy[node]);
lazy[node*2+1]=max(lazy[node*2+1], lazy[node]);
}
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, int k)
{
if(l>r) return;
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
}
void update2(int node, int tl, int tr, int p, int k)
{
busy(node, tl, tr);
if(tl==tr) { tree[node]=k; return; }
int mid=tl+tr>>1;
if(p<=mid) update2(node*2, tl, mid, p ,k);
else update2(node*2+1, mid+1, tr, p, k);
}
int query(int node, int tl, int tr, int p)
{
busy(node, tl, tr);
if(tl==tr) return tree[node];
int mid=tl+tr>>1;
if(p<=mid) return query(node*2, tl, mid, p);
else return query(node*2+1, mid+1, tr, p);
}
}segx, segy;
int main()
{
scanf("%d%d%d", &N, &M, &Q);
for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
for(int i=1; i<=Q; i++)
{
scanf("%d", &B[i].t);
if(B[i].t==1) scanf("%d", &B[i].p);
else if(B[i].t==2) scanf("%d", &B[i].x);
else if(B[i].t==3) scanf("%d", &B[i].x);
else if(B[i].t==4)
{
scanf("%d%d", &B[i].x, &B[i].y);
B[i].p=++M;
A[M]={B[i].x, B[i].y, M};
}
}
for(int i=1; i<=M; i++) segx.update2(1, 1, M, i, A[i].x);
for(int i=1; i<=M; i++) segy.update2(1, 1, M, i, A[i].y);
for(int i=1; i<=Q; i++)
{
if(B[i].t==1)
{
printf("%d %d\n", segx.query(1, 1, M, B[i].p), segy.query(1, 1, M, B[i].p));
}
else if(B[i].t==2)
{
int l, r;
int lo=0, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(segy.query(1, 1, M, mid)<=B[i].x) hi=mid;
else lo=mid;
}
l=hi;
lo=0, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(segx.query(1, 1, M, mid)<=N-B[i].x) lo=mid;
else hi=mid;
}
r=lo;
segx.update(1, 1, M, l, r, N-B[i].x);
}
else if(B[i].t==3)
{
int l, r;
int lo=0, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(segy.query(1, 1, M, mid)<=N-B[i].x) hi=mid;
else lo=mid;
}
l=hi;
lo=0, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(segx.query(1, 1, M, mid)<=B[i].x) lo=mid;
else hi=mid;
}
r=lo;
segy.update(1, 1, M, l, r, N-B[i].x);
}
}
}
Compilation message
sweeping.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
sweeping.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid=tl+tr>>1;
| ~~^~~
sweeping.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
sweeping.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid=tl+tr>>1;
| ~~^~~
sweeping.cpp: In member function 'int SEG::query(int, int, int, int)':
sweeping.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid=tl+tr>>1;
| ~~^~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:115:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int mid=lo+hi>>1;
| ~~^~~
sweeping.cpp:123:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mid=lo+hi>>1;
| ~~^~~
sweeping.cpp:136:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
136 | int mid=lo+hi>>1;
| ~~^~~
sweeping.cpp:144:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
144 | int mid=lo+hi>>1;
| ~~^~~
sweeping.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d%d%d", &N, &M, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d", &B[i].t);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:89:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | if(B[i].t==1) scanf("%d", &B[i].p);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | else if(B[i].t==2) scanf("%d", &B[i].x);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
91 | else if(B[i].t==3) scanf("%d", &B[i].x);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
94 | scanf("%d%d", &B[i].x, &B[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
94456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4580 ms |
127128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5811 ms |
125800 KB |
Output is correct |
| 2 |
Correct |
5752 ms |
145520 KB |
Output is correct |
| 3 |
Correct |
4999 ms |
144452 KB |
Output is correct |
| 4 |
Correct |
5359 ms |
145600 KB |
Output is correct |
| 5 |
Correct |
5227 ms |
145268 KB |
Output is correct |
| 6 |
Correct |
5427 ms |
145760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5811 ms |
125800 KB |
Output is correct |
| 2 |
Correct |
5752 ms |
145520 KB |
Output is correct |
| 3 |
Correct |
4999 ms |
144452 KB |
Output is correct |
| 4 |
Correct |
5359 ms |
145600 KB |
Output is correct |
| 5 |
Correct |
5227 ms |
145268 KB |
Output is correct |
| 6 |
Correct |
5427 ms |
145760 KB |
Output is correct |
| 7 |
Incorrect |
4805 ms |
145636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
94456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
