oj.uz

Submission #260947

# Submission time Handle Problem Language Result Execution time Memory
260947 2020-08-11T08:22:38 Z 반딧불(#5074) Sweeping (JOI20_sweeping) C++17
0 / 100
 1309 ms 38648 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];

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);
            printf("%d ~ %d\n", m+1-lim, lim2);
            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);
            printf("%d ~ %d\n", m+1-lim, lim2);
            Y.updateTree(1, 1, m, m+1-lim, lim2, n-x);
        }
    }
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:65: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:67: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:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qt);
         ~~~~~^~~~~~~~~~~
sweeping.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &p);
             ~~~~~^~~~~~~~~~
sweeping.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
sweeping.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 915 ms 28224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1309 ms 38648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 1309 ms 38648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -