Submission #964079

#	Time	Username	Problem	Language	Result	Execution time	Memory
964079		zxcigan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1194 ms	96584 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 1;
const int mod = 1e9 + 7;

template <typename T>
bool umx(T& a, T b) {
    return (a < b ? a = b, 1 : 0);
}
template <typename T>
bool umn(T& a, T b) {
    return (a > b ? a = b, 1 : 0);
}
int t[4 * N];
vector<array<int,3>> query[N];
void update (int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        umx (t[v], x);
        return;
    }
    int tm = (tr + tl) >> 1;
    if (pos <= tm) update (v << 1, tl, tm, pos, x);
    else update (v << 1 | 1, tm + 1, tr, pos, x);
    t[v] = max (t[v << 1], t[v << 1 | 1]);
}
int get (int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return t[v];
    int tm = (tr + tl) >> 1;
    return max (get (v << 1, tl, tm, l, min (r, tm)), get (v << 1 | 1, tm + 1, tr, max (l, tm + 1), r));
}
void solve () {
    int n, q;
    cin >> n >> q;
    vector<int> w (n + 1);
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= q; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        query[r].push_back ({l, k, i});
    }
    vector<int> ans (q + 1);
    vector<int> ve;
    for (int right = 1; right <= n; ++right) {
        while ((int)ve.size() && w[ve.back()] <= w[right]) {
            ve.pop_back();
        }
        if ((int)ve.size()) update (1, 1, n, ve.back(), w[right] + w[ve.back()]);
        ve.push_back(right);
        for (auto [l, k, i] : query[right]) {
            ans[i] = bool(get (1, 1, n, l, right) <= k);
        }
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
    cout << endl;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //    freopen ("input.txt", "r", stdin);
//    freopen ("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while (T--) 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