oj.uz

Submission #260953

# Submission time Handle Problem Language Result Execution time Memory
260953 2020-08-11T08:27:38 Z 반딧불(#5074) Sweeping (JOI20_sweeping) C++17
11 / 100
 1171 ms 31532 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];
            lazy[i] = -1;
            return;
        }
        int m = (l+r)>>1;
        lazy[i] = -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] == -1) return;
        tree[i] = lazy[i];
        if(l!=r) lazy[i*2] = lazy[i*2+1] = lazy[i];
        lazy[i] = -1;
    }
    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;
        propagate(i*2, l, m);
        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: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:94: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 775 ms 25464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 30968 KB Output is correct
2 Correct 1144 ms 31100 KB Output is correct
3 Correct 1000 ms 30692 KB Output is correct
4 Correct 1164 ms 31532 KB Output is correct
5 Correct 1110 ms 31224 KB Output is correct
6 Correct 1075 ms 31016 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 30968 KB Output is correct
2 Correct 1144 ms 31100 KB Output is correct
3 Correct 1000 ms 30692 KB Output is correct
4 Correct 1164 ms 31532 KB Output is correct
5 Correct 1110 ms 31224 KB Output is correct
6 Correct 1075 ms 31016 KB Output is correct
7 Incorrect 954 ms 31096 KB Output isn't correct
8 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 -