Submission #237432

#	Time	Username	Problem	Language	Result	Execution time	Memory
237432		TeaTime	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	512 ms	262144 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 long long 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 * 1e9, 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]));
            bst[v] = max(bst[v * 2 + 1], bst[v * 2 + 2]);
            ll q = 0;
            if (lower_bound(mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), tree[v * 2 + 1]) != mrg[v * 2 + 2].begin()) {
                q = *(--lower_bound(mrg[v * 2 + 2].begin(), mrg[v * 2 + 2].end(), tree[v * 2 + 1])) + tree[v * 2 + 1];
            }   
            bst[v] = max(bst[v], q);
        }
    }
     
    ll ask(int v, int l, int r, int askl, int askr, ll curMx = -1) {
        if (l >= askr || r <= askl) return 0;
     
        if (l >= askl && r <= askr) {
            ll q = 0;
            if (lower_bound(mrg[v].begin(), mrg[v].end(), curMx) != mrg[v].begin()) {
                q = *(--lower_bound(mrg[v].begin(), mrg[v].end(), curMx)) + curMx;
            }
            return max(q, bst[v]);
        }
     
        int mid = (l + r) / 2;
        return max(ask(v * 2 + 1, l, mid, askl, askr, curMx), ask(v * 2 + 2, mid, r, askl, askr, max(curMx, tree[v * 2 + 1])));
    }
     
    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;
            cout << (ask(0, 0, n, l - 1, r) <= k) << "\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