Submission #861719

#	Time	Username	Problem	Language	Result	Execution time	Memory
861719		Dec0Dedd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1947 ms	152292 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6+10;
const int INF = 1e9+100;

int w[N], k[N], lf[N], x[N], n, q;
vector<pii> v[N];
vector<int> evs[N];

struct segtree {
    vector<int> t;

    void init(int k) {
        int sz=1;
        while (sz < 4*k) sz*=2;
        t.resize(sz);
    }

    void upd(int v, int l, int r, int p, int val) {
        if (l == r) {
            t[v]=val;
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, val);
        else upd(2*v+1, m+1, r, p, val);
        t[v]=max(t[2*v], t[2*v+1]);
    }

    int que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

int main() {
    cin>>n>>q;
    for (int i=1; i<=n; ++i) cin>>w[i];

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

    segtree t; t.init(n+10);

    w[0]=INF;
    stack<int> st; st.push(0);
    for (int i=1; i<=n; ++i) {
        while (w[st.top()] <= w[i]) st.pop();
        lf[i]=st.top(); evs[st.top()].push_back(i);
        if (lf[i] > 0) t.upd(1, 1, n, i, w[st.top()]+w[i]);
        st.push(i);
    }

    for (int i=1; i<=n; ++i) {
        for (auto u : v[i]) x[u.second]=t.que(1, 1, n, i, u.first);
        for (auto u : evs[i]) t.upd(1, 1, n, u, 0);
    }

    for (int i=1; i<=q; ++i) {
        if (x[i] > k[i]) cout<<0<<"\n";
        else cout<<1<<"\n";
    }
}

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