Submission #237453

#	Time	Username	Problem	Language	Result	Execution time	Memory
237453		TeaTime	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3091 ms	252828 KiB

sortbooks

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <unordered_set>
#include <map>
#include <string>
#include <cmath>
#include <queue>
#include <ctime>
#include <set>

using namespace std;

typedef int ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define pb push_back
#define all(x) (x).begin(),(x).end()

const ll SIZE = 1e6 + 10, INF = 1e9 + 10, MOD = 1e9 + 7;

ll tree[SIZE * 4], bst[SIZE * 4];
vector<ll> mrg[SIZE * 4];
vector<ll> vec;

void build(int v, int l, int r) {
    if (l == r - 1) {
        tree[v] = vec[l];
        mrg[v].pb(vec[l]);
        bst[v] = 0;
    }
    else {
        int mid = (l + r) / 2;
        build(v * 2 + 1, l, mid);
        build(v * 2 + 2, mid, r);
        tree[v] = max(tree[v * 2 + 1], tree[v * 2 + 2]);
        merge(mrg[v * 2 + 1].begin(), mrg[v * 2 + 1].end(), mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), std::back_inserter(mrg[v]));
        auto k = unique(all(mrg[v]));
        mrg[v].erase(k, mrg[v].end());
        bst[v] = max(bst[v * 2 + 1], bst[v * 2 + 2]);
        ll q = 0;
        auto it = lower_bound(mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), tree[v * 2 + 1]);
        if (it != mrg[v * 2 + 2].begin()) {
            q = *(--it) + tree[v * 2 + 1];
        }
        bst[v] = max(bst[v], q);
    }
}

pair<ll, ll> ask(int v, int l, int r, int askl, int askr, ll curMx = -1) {
    if (l >= askr || r <= askl) return { 0, -1 };

    if (l >= askl && r <= askr) {
        ll q = 0;
        auto it = lower_bound(mrg[v].begin(), mrg[v].end(), curMx);
        if (it != mrg[v].begin()) {
            q = *(--it) + curMx;
        }
        return { max(q, bst[v]), tree[v] };
    }

    int mid = (l + r) / 2;
    pair<ll, ll> q = ask(v * 2 + 1, l, mid, askl, askr, curMx), q2 = ask(v * 2 + 2, mid, r, askl, askr, max(curMx, q.second));
    pair<ll, ll> ans;
    ans.first = max(q.first, q2.first);
    ans.second = max(max(q.second, q2.second), curMx);
    return ans;
}

int main() {
    fastInp;

    ll n, m;
    cin >> n >> m;
    vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    build(0, 0, n);

    while (m--) {
        ll l, r, k;
        cin >> l >> r >> k;
        if ((ask(0, 0, n, l - 1, r).first <= k)) {
            cout << "1\n";
        }
        else {
            cout << "0\n";
        }
    }

    return 0;
}

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