oj.uz

Submission #599186

# Submission time Handle Problem Language Result Execution time Memory
599186 2022-07-19T11:25:38 Z M_W Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 14652 KB 
    #include <bits/stdc++.h>
    #define ii pair<int, int>
    using namespace std;
    int t[1000001 << 2];
    int a[1000001];
     
    void build(int v, int l, int r){
        if(l == r){
            t[v] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(v * 2, l, mid); build(v * 2 + 1, mid + 1, r);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
     
    int query(int v, int tl, int tr, int l, int r){
        if(l > r) return -1;
        if(tl == l && tr == r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }
     
    int main(){
        int N, M;
        scanf("%d %d", &N, &M);
        for(int i = 1; i <= N; i++){
            scanf("%d", &a[i]);
        }
        build(1, 1, N);
        while(M--){
            int a, b, k;
            scanf("%d %d %d", &a, &b, &k);
            int l = a, r = b;
     
            while(l < r){
                int mid = (l + r) >> 1;
                int ll = query(1, 1, N, a, mid), rr = query(1, 1, N, mid + 1, b);
                if(ll <= rr) l = mid + 1;
                else r = mid;
            }
            int ll = query(1, 1, N, a, l), rr = query(1, 1, N, l + 1, b);
            if(rr != -1 && ll + rr > k) printf("0\n");
            else printf("1\n");
        }
    }

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d %d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             scanf("%d", &a[i]);
      |             ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%d %d %d", &a, &b, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 14652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -