Submission #146163

#	Time	Username	Problem	Language	Result	Execution time	Memory
146163		imeimi2000	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	926 ms	100168 KiB

sortbooks

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;

struct _qs {
    int l, r, k, i;
    void scan(int idx) {
        i = idx;
        cin >> l >> r >> k;
    }
    bool operator<(const _qs &p) const {
        return l > p.l;
    }
} qs[1000000];
bool ans[1000000];

int n, q;
int W[1000001];
int fen[1000001];

void update(int i, int x) {
    while (i <= n) {
        fen[i] = max(fen[i], x);
        i += i & -i;
    }
}

int query(int i) {
    int r = 0;
    while (i) {
        r = max(r, fen[i]);
        i -= i & -i;
    }
    return r;
}

vector<int> R[1000001];

void add(int l, int r) {
    R[l].push_back(r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> W[i];
    vector<int> st;
    for (int i = n; i > 0; --i) {
        while (!st.empty() && W[st.back()] < W[i]) {
            add(i, st.back());
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 0; i < q; ++i) qs[i].scan(i);
    sort(qs, qs + q);
    for (int i = 0, j = n + 1; i < q; ++i) {
        while (qs[i].l < j) {
            for (int k : R[--j]) {
                update(k, W[j] + W[k]);
            }
        }
        ans[qs[i].i] = query(qs[i].r) <= qs[i].k;
    }
    for (int i = 0; i < q; ++i) printf("%d\n", (int)ans[i]);
    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