Submission #1111631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111631		Pekiban	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2249 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
vector<int> st[4*N];
int mx[4*N], n;
void build(vector<int> &a, int i = 1, int l2 = 1, int r2 = n) {
    if (l2 == r2) {
        st[i]= {a[l2]};
        mx[i] = 0;
        return;
    }
    int m2 = (l2 + r2)/2;
    build(a, 2*i, l2, m2);
    build(a, 2*i+1, m2+1, r2);
    st[i].resize(r2 - l2 + 1);
    merge(st[2*i].begin(), st[2*i].end(), st[2*i+1].begin(), st[2*i+1].end(), st[i].begin());
    int id = upper_bound(st[2*i+1].begin(), st[2*i+1].end(), st[2*i].back()-1) - st[2*i+1].begin();
    if (!id)    mx[i] = max(mx[2*i], mx[2*i+1]);
    else {
        mx[i] = max({mx[2*i], mx[2*i+1], st[2*i].back() + st[2*i+1][id-1]});
    }
}
int M = 0, MS = 0;
void qry(int l, int r, int i = 1, int l2 = 1, int r2 = n) {
    if (l <= l2 && r2 <= r) {
        int id = upper_bound(st[i].begin(), st[i].end(), M-1) - st[i].begin();
        MS = max(MS, mx[i]);
        if (id) MS = max({MS, M + st[i][id-1]});
        M = max(M, st[i].back());
        return;
    }
    int m2 = (l2 + r2)/2;
    if (l <= m2)    qry(l, r, 2*i, l2, m2);
    if (m2 +1 <= r) qry(l, r, 2*i+1, m2+1, r2);   
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> n >> m;
    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(a);
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        M = 0, MS = 0;
        qry(l, r);
        cout << (MS <= k) << '\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