Submission #1112991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112991		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1981 ms	96584 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e6 + 5;
 
int tree[4*maxn], n, q;
 
void U(int u, int tl, int tr, int p, int v) {
    if(tl == tr) {
        tree[u] = max(tree[u], v);
    } else {
        int tm = (tl + tr) / 2;
        if(p <= tm) U(2*u, tl, tm, p, v);
        else U(2*u+1, tm+1, tr, p, v);
        tree[u] = max(tree[2*u], tree[2*u+1]);
    }
}
 
int Q(int u, int tl, int tr, int l, int r) {
    if(l > tr || tl > r) return 0;
    if(l <= tl && tr <= r) return tree[u];
    int tm = (tl + tr) / 2;
    return max(Q(2*u, tl, tm, l, r), Q(2*u+1, tm+1, tr, l, r));
}
 
int main() {
    cin >> n >> q;
 
    vector<int> v(n+1), ans(q);
    for(int i=1; i<=n; i++) cin >> v[i];
 
    vector<array<int, 3> > qus[n+1];
    for(int i=0; i<q; i++) {
        int l, r, k; cin >> l >> r >> k;
        qus[r].push_back({ l, k, i });
    }
 
    stack<int> st;
    for(int i=1; i<=n; i++) {
        while(!st.empty() && v[st.top()] <= v[i]) st.pop();
        if(!st.empty()) U(1, 1, n, st.top(), v[st.top()] + v[i]);
        for(auto &[l, k, id] : qus[i]) ans[id] = (Q(1, 1, n, l, i) <= k);
        st.push(i);
    }
 
    for(int x : ans) cout << x << '\n';
    return 0;
}

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