Submission #1072149

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

sortbooks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e6 + 5;
const int M = 1e6 + 6;
const int B = 450;

struct Query {
    ll l, mood, id;
};

ll n, m, a[N], pos[N];
vector <Query> g[N];
ll ans[N];
ll t[N * 4];

void upd(int pos, ll val, int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
        t[v] = max(t[v], val);
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) upd(pos, val, v + v, tl, tm);
    else upd(pos, val, v + v + 1, tm + 1, tr);
    t[v] = max(t[v + v], t[v + v + 1]);
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }

    stack <int> st;
    for (int i = 1; i <= n; ++ i) {
        while (st.size() && a[st.top()] <= a[i]) st.pop();

        if (st.size() > 0) pos[i] = st.top();
        else pos[i] = 0;

        st.push(i);
    }

    for (int i = 1; i <= m; ++ i) {
        int l, r, mood;
        cin >> l >> r >> mood;
        g[r].push_back({l, mood, i});
    }

    for (int i = 1; i <= n; ++ i) {
        if (pos[i] > 0) upd(pos[i], a[pos[i]] + a[i]);
        for (auto [l, mood, id] : g[i]) {
            if (get(l, i) <= mood) ans[id] = 1;
            else ans[id] = 0;
        }
    }

    for (int i = 1; i <= m; ++ i) cout << ans[i] << "\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