Submission #1178170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178170		nguyenkhangninh99	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	616 ms	92672 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e6 + 5;

vector<array<int, 3>> query[maxn];

struct FenwickTree{
    vector<int> tree;
    void init(int sz){
        tree.assign(sz + 2, 0);
    }
    void update(int id, int val){
        while(id > 0){
            tree[id] = max(tree[id], val);
            id -= (id & -id);
        }
    }

    int get(int id){
        int res = 0;
        while(id < tree.size()){
            res = max(res, tree[id]);
            id += (id & -id);
        }
        return res;
    }
} bit;

void solve(){
    int n, q; cin >> n >> q;

    vector<int> a(n + 1), l(n + 1, -1), ans(q + 1);
    bit.init(n + 1);
    stack<int> st;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        while(st.size() && a[st.top()] <= a[i]) st.pop();
        if(st.size()) l[i] = st.top();
        st.push(i);
    }

    for(int i = 1; i <= q; i++){
        int l, r, k; cin >> l >> r >> k;
        query[r].push_back({l, k, i});
    }

    for(int i = 1; i <= n; i++){
        if(l[i] >= 1) bit.update(l[i], a[l[i]] + a[i]);
        for(auto [left, k, id]: query[i]){
            if(bit.get(left) <= k) ans[id] = 1;
        }
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23