Submission #1285114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285114		dobri_oke	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	2068 ms	201396 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back

const int N = 1e6 + 100;
int n, q, a[N];
int t[N * 4], t2[N * 4];
vector<int> g[N * 4];

// Построение сегментного дерева
void build(int v, int l, int r) {
    if (l == r) {
        t[v] = a[l];
        g[v] = {a[l]};
        t2[v] = -1e9;
        return;
    }

    int m = (l + r) >> 1;
    build(v << 1, l, m);
    build(v << 1 | 1, m + 1, r);

    auto &L = g[v << 1];
    auto &R = g[v << 1 | 1];
    g[v].resize(L.size() + R.size());
    merge(L.begin(), L.end(), R.begin(), R.end(), g[v].begin());

    t[v] = max(t[v << 1], t[v << 1 | 1]);
    t2[v] = max(t2[v << 1], t2[v << 1 | 1]);

    int leftMax = t[v << 1];
    int pos = upper_bound(R.begin(), R.end(), leftMax - 1) - R.begin() - 1;
    if (pos >= 0)
        t2[v] = max(t2[v], leftMax + R[pos]);
}

// Запрос: возвращает {максимум, лучшая пара}
pair<int, int> get(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql)
        return {-1e9, -1e9};
    if (ql <= l && r <= qr)
        return {t[v], t2[v]};

    int m = (l + r) >> 1;
    auto L = get(v << 1, l, m, ql, qr);
    auto R = get(v << 1 | 1, m + 1, r, ql, qr);

    int mx = max(L.first, R.first);
    int best = max(L.second, R.second);

    // если максимум слева > минимум справа
    if (L.first != -1e9 && R.first != -1e9) {
        // ищем в правом подотрезке число < L.first
        auto &vecR = g[v << 1 | 1];
        int pos = upper_bound(vecR.begin(), vecR.end(), L.first - 1) - vecR.begin() - 1;
        if (pos >= 0)
            best = max(best, L.first + vecR[pos]);
    }

    return {mx, best};
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);

    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        if (l == r) {
            cout << 1 << "\n";
            continue;
        }
        auto res = get(1, 1, n, l, r);
        cout << (res.second <= k ? 1 : 0) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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