Submission #331846

#	Time	Username	Problem	Language	Result	Execution time	Memory
331846		keko37	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2301 ms	95748 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
const int INF = 1000000007;

int n, m, ofs = 1;
int w[MAXN], lef[MAXN], rig[MAXN], mood[MAXN], ans[MAXN];
int t[MAXN * 4], mx[MAXN * 4];
vector <int> v[MAXN], r;

void build () {
    for (int i = 0; i < 2 * ofs; i++) mx[i] = -INF;
    for (int i = 0; i < n; i++) mx[i + ofs] = w[i];
    for (int i = ofs - 1; i > 0; i--) {
        mx[i] = max(mx[2 * i], mx[2 * i + 1]);
    }
}

void update (int pos, int val) {
    pos += ofs;
    t[pos] = val;
    pos /= 2;
    while (pos > 0) {
        t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
        pos /= 2;
    }
}

int upit (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return t[x];
    if (to < lo || hi < from) return -INF;
    return max(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

int upit_mx (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return mx[x];
    if (to < lo || hi < from) return -INF;
    return max(upit_mx(2 * x, from, to, lo, (lo + hi) / 2), upit_mx(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    while (ofs < n) ofs *= 2;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    build();
    for (int i = 0; i < m; i++) {
        cin >> lef[i] >> rig[i] >> mood[i];
        lef[i]--; rig[i]--;
        v[lef[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; i--) {
        int val = -INF;
        while (!r.empty() && w[i] > w[-r.back()]) {
            val = max(val, w[-r.back()]);
            update(-r.back(), -INF);
            r.pop_back();
        }
        update(i, w[i] + val);
        r.push_back(-i);

        for (int q : v[i]) {
            int pos = -*lower_bound(r.begin(), r.end(), -rig[q]);
            ans[q] = -INF;
            if (i < pos) ans[q] = max(ans[q], upit(1, i, pos - 1, 0, ofs - 1));
            if (pos < rig[q]) ans[q] = max(ans[q], w[pos] + upit_mx(1, pos + 1, rig[q], 0, ofs - 1));
        }
    }
    for (int i = 0; i < m; i++) {
        cout << (ans[i] <= mood[i]) << '\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