| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 800030 |
2023-08-01T09:29:38 Z |
반딧불(#10081) |
Sweeping (JOI20_sweeping) |
C++17 |
|
1049 ms |
54220 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
int x, y, idx;
Point(){}
bool operator<(const Point &r)const{
if(x != r.x) return x < r.x;
return y > r.y;
}
};
struct segTree{
int x[1<<20], y[1<<20];
int lazyX[1<<20], lazyY[1<<20];
void init(int i, int l, int r, Point *arr){
if(l==r){
x[i] = arr[l].x, y[i] = arr[l].y;
return;
}
int m = (l+r)>>1;
init(i*2, l, m, arr);
init(i*2+1, m+1, r, arr);
x[i] = max(x[i*2], x[i*2+1]);
y[i] = max(y[i*2], y[i*2+1]);
}
void propagate(int i, int l, int r){
x[i] = max(x[i], lazyX[i]), y[i] = max(y[i], lazyY[i]);
if(l!=r){
lazyX[i*2] = max(lazyX[i], lazyX[i*2]), lazyX[i*2+1] = max(lazyX[i], lazyX[i*2+1]);
lazyY[i*2] = max(lazyY[i], lazyY[i*2]), lazyY[i*2+1] = max(lazyY[i], lazyY[i*2+1]);
}
lazyX[i] = 0, lazyY[i] = 0;
}
void print(int i, int l, int r, int w){
propagate(i, l, r);
if(l==r){
printf("%d %d\n", x[i], y[i]);
return;
}
int m = (l+r)>>1;
if(w<=m) print(i*2, l, m, w), propagate(i*2+1, m+1, r);
if(m<w) print(i*2+1, m+1, r, w), propagate(i*2, l, m);
}
void updateX(int i, int l, int r, int ylim, int to){
propagate(i, l, r);
if(y[i] <= ylim){
lazyX[i] = to;
propagate(i, l, r);
return;
}
if(l==r) return;
int m = (l+r)>>1;
updateX(i*2, l, m, ylim, to);
if(y[i*2] <= ylim) updateX(i*2+1, m+1, r, ylim, to);
}
void updateY(int i, int l, int r, int xlim, int to){
propagate(i, l, r);
if(x[i] <= xlim){
lazyY[i] = to;
propagate(i, l, r);
return;
}
if(l==r) return;
int m = (l+r)>>1;
updateY(i*2, l, m, xlim, to);
if(x[i*2] <= xlim) updateY(i*2+1, m+1, r, xlim, to);
}
} tree;
int L, n, q;
Point arr[500002];
int idx[500002];
int main(){
scanf("%d %d %d", &L, &n, &q);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++) idx[arr[i].idx] = i;
tree.init(1, 1, n, arr);
while(q--){
int qt, qa;
scanf("%d %d", &qt, &qa);
if(qt==1){
tree.print(1, 1, n, idx[qa]);
}
else if(qt==2){
tree.updateX(1, 1, n, qa, L-qa);
}
else if(qt==3){
tree.updateY(1, 1, n, qa, L-qa);
}
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d %d %d", &L, &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d %d", &qt, &qa);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
662 ms |
49476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1049 ms |
54220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1049 ms |
54220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
