Submission #1283600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283600		peteza	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2912 ms	191720 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxn = 1e6+5;

int segm[mxn*4];
vector<int> segvec[mxn*4];

int n, m, arr[mxn], a, b, c;

void dfsseg(int idx, int l, int r) {
    for(int i=l;i<=r;i++) {
        segvec[idx].push_back(arr[i]);
    }
    if(l == r) return;
    sort(segvec[idx].begin(), segvec[idx].end());
    int mid = (l+r) >> 1;
    dfsseg(idx*2+1, l, mid);
    dfsseg(idx*2+2, mid+1, r);
    segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
    auto it = lower_bound(segvec[idx*2+2].begin(), segvec[idx*2+2].end(), segvec[idx*2+1].back());
    if(it != segvec[idx*2+2].begin()) {
        it--;
        segm[idx] = max(segm[idx], *it + segvec[idx*2+1].back());
    }
}

int cmx = 0;
int cval = -1000000000;

void qr(int idx, int l, int r, int tl, int tr) {
    if(tr < l || r < tl) return ;
    if(tl <= l && r <= tr) {
        cmx = max(cmx, segm[idx]);
        auto it = lower_bound(segvec[idx].begin(), segvec[idx].end(), cval);
        if(it != segvec[idx].begin()) {
            it--;
            cmx = max(cmx, *it + cval);
        }
        cval = max(cval, segvec[idx].back());
        return ;
    }
    int mid = (l+r) >> 1;
    qr(idx*2+1, l, mid, tl, tr);
    qr(idx*2+2, mid+1, r, tl, tr);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> arr[i];
    dfsseg(0, 1, n);
    while(m--) {
        cin >> a >> b >> c;
        cmx = 0; cval = -1000000000;
        qr(0, 1, n, a, b);
        cout << (cmx <= c) << '\n';
    }
}

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