oj.uz

Submission #1110592

# Submission time Handle Problem Language Result Execution time Memory
1110592 2024-11-10T03:47:09 Z Zero_OP Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 913 ms 83044 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

struct segment_tree{
    vector<int> st;
    segment_tree(int n) : st(n << 2) {}

    void update(int id, int l, int r, int u, int v, int val){
        st[id] = max(st[id], val);
        if(u <= l && r <= v) return;
        int mid = l + r >> 1;
        if(u <= mid) update(id << 1, l, mid, u, v, val);
        if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
    }

    int query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> a(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }

    vector<vector<tuple<int, int, int>>> sweep(N);
    for(int i = 0; i < M; ++i){
        int l, r, k;
        cin >> l >> r >> k;
        --l, --r;
        sweep[r].emplace_back(l, k, i);
    }

    vector<bool> answer(M, false);

    segment_tree tree(N);
    stack<int> st;
    for(int i = 0; i < N; ++i){
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(!st.empty()) tree.update(1, 0, N - 1, st.top(), i, a[st.top()] + a[i]);

        for(auto [j, k, id] : sweep[i]){
            answer[id] = (tree.query(1, 0, N - 1, j, i) <= k);
        }

        st.push(i);
    }

    for(auto it : answer) cout << it << '\n';

    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
sortbooks.cpp:14:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         int mid = l + r >> 1;
      |                   ~~^~~
sortbooks.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
sortbooks.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = l + r >> 1;
      |                   ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for(auto [j, k, id] : sweep[i]){
      |                  ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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