oj.uz

답안 #800030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800030 2023-08-01T09:29:38 Z 반딧불(#10081) 청소 (JOI20_sweeping) C++17
0 / 100
 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 662 ms 49476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1049 ms 54220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1049 ms 54220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 548 KB Output isn't correct
2 Halted 0 ms 0 KB -