Submission #1119347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119347		Thunnus	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1868 ms	262144 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

/*
One key observation to make is that if at our current
index i and there exists a j where i < j and w_i <= w_j, then we can't
increase the value of any inversion pairs where the second value's index is greater than j.
*/

struct SegTree{
    struct Node{
        int lazy = -1, max = 0, ans = 0;
        Node () {}
        Node(int l, int m, int a) : lazy(l), max(m), ans(a) {}
    };
    vector<Node> st;
    SegTree(int n) : st(4 * n) {}

    inline Node combine(const Node &a, const Node &b){
        Node c;
        c.max = max(a.max, b.max);
        c.ans = max(a.ans, b.ans);
        return c;
    }

    inline void apply(int v, int val){
        st[v].lazy = val;
        st[v].ans = st[v].max + val;
        return;
    }

    inline void propagate(int v){
		if(st[v].lazy == -1) return;
        apply(2 * v, st[v].lazy);
        apply(2 * v + 1, st[v].lazy);
        st[v].lazy = -1;
        return;
    }

    inline void build(const vi &ar, int v, int tl, int tr){
        if(tl == tr){
            st[v] = Node(-1, ar[tl - 1], 0);
            return;
        }
        int mid = (tl + tr) / 2;
        build(ar, 2 * v, tl, mid);
        build(ar, 2 * v + 1, mid + 1, tr);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        cout << "v: " << v << " tl: " << tl << " tr: " << tr << " Node: " << st[v].lazy << " " << st[v].max << " " << st[v].ans << "\n";
        return;
    }

    inline void update(int ul, int ur, int val, int v, int tl, int tr){
        if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            apply(v, val);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        update(ul, ur, val, 2 * v, tl, mid);
        update(ul, ur, val, 2 * v + 1, mid + 1, tr);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        cout << "update: v: " << v << " tl: " << tl << " tr: " << tr << " Node: " << st[v].lazy << " " << st[v].max << " " << st[v].ans << "\n";
        return;
    }

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return Node(-1, -1, -1);
        if(ql <= tl && tr <= qr) return st[v];
        int mid = (tl + tr) / 2;
        propagate(v);
        cout << "query: " << "v: " << v << " tl: " << tl << " tr: " << tr << " Node: " << st[v].lazy << " " << st[v].max << " " << st[v].ans << "\n";
        return combine(query(ql, qr, 2 * v, tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr));
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, l, r, x;
    cin >> n >> q;
    vi a(n);
    for(int &i : a){
        cin >> i;
    }
    vector<vector<array<int, 3>>> l2q(n);
    for(int i = 0; i < q; i++){
        cin >> l >> r >> x;
        l--, r--;
        l2q[l].push_back({r, x, i});
    }

    stack<int> sta;
    SegTree st(n + 1);
    vi ans(q);
    st.build(a, 1, 1, n);
    for(int i = n - 1; i >= 0; i--){
        while(!sta.empty() && a[sta.top()] < a[i]){
            sta.pop();
        }
        int till = (sta.empty() ? n + 1 : sta.top());
        st.update(i + 2, till, a[i], 1, 1, n);

        for(array<int, 3> &qu : l2q[i]){
            ans[qu[2]] = st.query(i + 1, qu[0] + 1, 1, 1, n).ans <= qu[1];
        }
        sta.emplace(i);
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    cout << "\n";
    return 0;
}

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