Submission #1156856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156856		Hamed_Ghaffari	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	807 ms	68732 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

#define maxs(a,b) (a=max(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back

const int MXN = 1e6+5;

int n, seg[MXN<<2];
void upd(int p, int x, int l=1, int r=n+1, int id=1) {
    if(r-l==1) {
        maxs(seg[id], x);
        return;
    }
    if(p<mid) upd(p, x, l, mid, lc);
    else upd(p, x, mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
}
int get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int L[MXN], K[MXN], q, lf[MXN], a[MXN];
bool ans[MXN];
vector<int> Q[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        for(lf[i]=i-1; lf[i]&&a[lf[i]]<=a[i]; lf[i]=lf[lf[i]]);
    }
    for(int i=1, r; i<=q; i++) {
        cin >> L[i] >> r >> K[i];
        Q[r].pb(i);
    }
    for(int i=1; i<=n; i++) {
        if(lf[i]) upd(lf[i], a[lf[i]]+a[i]);
        for(int j : Q[i])
            ans[j] = K[j]>=get(L[j], i+1);
    }
    for(int i=1; i<=q; i++) cout << ans[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