Submission #1084991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084991		makrav	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1914 ms	186436 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

struct node {
    int mval, ans, push;
    node() = default;
    node(int mval_, int ans_) {
        mval = mval_;
        ans = ans_;
        push = 0;
    }
};

node operator+(node x, node y) {
    return node(max(x.mval, y.mval), max(x.ans, y.ans));
}

struct segtree {
    int n;
    vector<node> t;
    vector<int> a;
    segtree() = default;
    segtree(int n_, vector<int> a_) {
        n = n_;
        a = a_;
        t.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = node(a[tl], 0);
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    
    void push(int v, int tl, int tr) {
        if (t[v].push > 0) {
            t[v].ans = t[v].mval + t[v].push;
            if (tl + 1 < tr) {
                t[v * 2].push = t[v].push;
                t[v * 2 + 1].push = t[v].push;
            }
            t[v].push = 0;
            return;
        }
        if (tl + 1 == tr) return;
        int vll = (t[v * 2].push ? t[v * 2].push + t[v * 2].mval : t[v * 2].ans), vlr = (t[v * 2 + 1].push ? t[v * 2 + 1].push + t[v * 2 + 1].mval : t[v * 2 + 1].ans);
        t[v].ans = max(vll, vlr);
    }   

    void upd(int v, int tl, int tr, int l, int r, int x) {
        push(v, tl, tr);
        if (l <= tl && tr <= r) {
            t[v].push = x;
            return;
        }
        if (tr <= l || tl >= r) return;
        int tm = (tl + tr) / 2;
        upd(v * 2, tl, tm, l, r, x); upd(v * 2 + 1, tm, tr, l, r, x);
        push(v, tl, tr);
    }

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

void solve() {
    int n, q; cin >> n >> q;
    vector<int> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    vector<vector<vector<int>>> reqs(n);
    for (int i = 0; i < q; i++) {
        int l, r, k; cin >> l >> r >> k;
        l--; r--;
        reqs[l].pb({i, r, k});
    }
    vector<int> ans(q, 1);
    segtree sg(n, w);
    stack<int> st;
    st.push(n - 1);
    for (int i = n - 2; i >= 0; i--) {
        while (!st.empty() && w[i] > w[st.top()]) {
            st.pop();
        }
        int nxt = (st.empty() ? n : st.top());
        if (nxt - i > 1) {
            sg.upd(1, 0, n, i + 1, nxt, w[i]);
        }
        st.push(i);
        for (auto u : reqs[i]) {
            int mx_n = sg.get(1, 0, n, i, u[1] + 1).ans;
            ans[u[0]] = (mx_n <= u[2]);
        }
    }
    for (auto &u : ans) cout << u << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    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