Submission #260927

# Submission time Handle Problem Language Result Execution time Memory
260927 2020-08-11T08:09:28 Z 반딧불(#5074) Sweeping (JOI20_sweeping) C++17
0 / 100
1182 ms 30824 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[6000002];
    int lazy[6000002];

    void initialize(int i, int l, int r, int A[]){
        if(l==r){
            tree[i] = A[l];
            return;
        }
        int m = (l+r)>>1;
        initialize(i*2, l, m, A);
        initialize(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        tree[i] = lazy[i];
        if(l!=r) lazy[i*2] = lazy[i*2+1] = lazy[i];
        lazy[i] = 0;
    }
    void updateTree(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(s>e) return;
        if(l==s && r==e){
            lazy[i] = val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        if(s<=m) updateTree(i*2, l, m, s, min(m, e), val);
        else propagate(i*2, l, m);
        if(m<e) updateTree(i*2+1, m+1, r, max(s, m+1), e, val);
        else propagate(i*2+1, m+1, r);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
    int getTree(int i, int l, int r, int idx){
        propagate(i, l, r);
        if(l==r) return tree[i];
        int m = (l+r)>>1;
        if(idx<=m) return getTree(i*2, l, m, idx);
        return getTree(i*2+1, m+1, r, idx);
    }
    int lowerBound(int i, int l, int r, int val){
        propagate(i, l, r);
        if(l==r){
            if(tree[i] <= val) return l;
            return l-1;
        }
        int m = (l+r)>>1;
        if(tree[i*2] <= val) return lowerBound(i*2+1, m+1, r, val);
        return lowerBound(i*2, l, m, val);
    }
} X, Y;

int n, m, q;
int x[1500002], y[1500002];
map<int, int> mp;



int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d %d", &x[i], &y[m+1-i]);
    }
    X.initialize(1, 1, m, x);
    Y.initialize(1, 1, m, y);

    for(int i=1; i<=q; i++){
        int qt;
        scanf("%d", &qt);
        if(qt == 1){
            int p;
            scanf("%d", &p);
            printf("%d %d\n", X.getTree(1, 1, m, p), Y.getTree(1, 1, m, m+1-p));
        }
        else if(qt==2){
            int x;
            scanf("%d", &x);

            int lim = Y.lowerBound(1, 1, m, x);
            int lim2 = X.lowerBound(1, 1, m, n-x);
            X.updateTree(1, 1, m, m+1-lim, lim2, n-x);
        }
        else{
            int x;
            scanf("%d", &x);

            int lim = X.lowerBound(1, 1, m, x);
            int lim2 = Y.lowerBound(1, 1, m, n-x);
            Y.updateTree(1, 1, m, m+1-lim, lim2, n-x);
        }
    }
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:68:10: 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:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x[i], &y[m+1-i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qt);
         ~~~~~^~~~~~~~~~~
sweeping.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &p);
             ~~~~~^~~~~~~~~~
sweeping.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
sweeping.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 751 ms 17360 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1182 ms 30824 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1182 ms 30824 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -