제출 #1061659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061659		VMaksimoski008	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	935 ms	96784 KiB

sortbooks

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e6 + 5;

int tree[4*maxn+5];

void update(int u, int tl, int tr, int p, int v) {
    if(tl == tr) {
        tree[u] = max(tree[u], v);
    } else {
        int tm = (tl + tr) / 2;
        if(p <= tm) update(2*u, tl, tm, p, v);
        else update(2*u+1, tm+1, tr, p, v);
        tree[u] = max(tree[2*u], tree[2*u+1]);
    }
}

int query(int u, int tl, int tr, int l, int r) {
    if(l > tr || tl > r) return 0;
    if(l <= tl && tr <= r) return tree[u];
    int tm = (tl + tr) / 2;
    return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
}

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

    int n, q;
    cin >> n >> q;

    vector<int> v(n+1), ans(q);
    for(int i=1; i<=n; i++) cin >> v[i];

    vector<array<int, 3> > qus[n+1];
    for(int i=0; i<q; i++) {
        int l, r, k; cin >> l >> r >> k;
        qus[r].push_back({ l, k, i });
    }

    stack<pii> st;
    for(int i=1; i<=n; i++) {
        while(!st.empty() && st.top().first <= v[i]) st.pop();
        if(!st.empty()) update(1, 1, n, st.top().second, st.top().first + v[i]);
        for(auto &[l, k, id] : qus[i]) ans[id] = (query(1, 1, n, l, i) <= k);
        st.push({ v[i], i });
    }

    for(int x : ans) cout << x << '\n';
    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