#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e9;
const int MAXM = 5e5;
const int MAXQ = 1e6;
struct Point
{
int x, y;
};
int N, M, Q;
Point A[MAXM+10];
Point tree[MAXM*4+10];
void update(int node, int tl, int tr, int l, int r, Point p)
{
if(l>r) return;
if(l<=tl && tr<=r)
{
tree[node].x=max(tree[node].x, p.x);
tree[node].y=max(tree[node].y, p.y);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, p);
update(node*2+1, mid+1, tr, l, r, p);
}
Point query(int node, int tl, int tr, int p)
{
if(tl==tr) return tree[node];
tree[node*2].x=max(tree[node*2].x, tree[node].x);
tree[node*2].y=max(tree[node*2].y, tree[node].y);
tree[node*2+1].x=max(tree[node*2+1].x, tree[node].x);
tree[node*2+1].y=max(tree[node*2+1].y, tree[node].y);
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);
}
int main()
{
int i, j;
scanf("%d%d%d", &N, &M, &Q);
for(i=1; i<=M; i++)
{
scanf("%d%d", &A[i].x, &A[i].y);
update(1, 1, M, i, i, A[i]);
}
for(i=1; i<=Q; i++)
{
int t;
scanf("%d", &t);
if(t==1)
{
int p; Point r;
scanf("%d", &p);
r=query(1, 1, M, p);
printf("%d %d\n", r.x, r.y);
}
else if(t==2)
{
int l, r, k;
scanf("%d", &k);
int lo=0, hi=M;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 1, M, mid).y>k) lo=mid;
else hi=mid;
}
l=hi;
lo=1, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 1, M, mid).x<=N-k) lo=mid;
else hi=mid;
}
r=lo;
update(1, 1, M, l, r, {N-k, 0});
}
else if(t==3)
{
int l, r, k;
scanf("%d", &k);
int lo=0, hi=M;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 1, M, mid).y>N-k) lo=mid;
else hi=mid;
}
l=hi;
lo=1, hi=M+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 1, M, mid).x<=k) lo=mid;
else hi=mid;
}
r=lo;
update(1, 1, M, l, r, {0, N-k});
}
}
}
Compilation message
sweeping.cpp: In function 'void update(int, int, int, int, int, Point)':
sweeping.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
sweeping.cpp: In function 'Point query(int, int, int, int)':
sweeping.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
sweeping.cpp:88:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
sweeping.cpp:104:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
sweeping.cpp:113:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
sweeping.cpp:52:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
sweeping.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &M, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i].x, &A[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
sweeping.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
sweeping.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
sweeping.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2152 ms |
20988 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3222 ms |
22488 KB |
Output is correct |
2 |
Correct |
3160 ms |
22412 KB |
Output is correct |
3 |
Correct |
2627 ms |
22036 KB |
Output is correct |
4 |
Correct |
2789 ms |
22592 KB |
Output is correct |
5 |
Incorrect |
3052 ms |
22620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3222 ms |
22488 KB |
Output is correct |
2 |
Correct |
3160 ms |
22412 KB |
Output is correct |
3 |
Correct |
2627 ms |
22036 KB |
Output is correct |
4 |
Correct |
2789 ms |
22592 KB |
Output is correct |
5 |
Incorrect |
3052 ms |
22620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |