Submission #1216135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216135		nh0902	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	429 ms	60932 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 10;

int n, m, q, w[N];

unordered_map<int ,int> pos;

//persistent tree

int child[4 * N][2];
int persis_st[4 * N], st_max_pair[4 * N];
int cur, ver[N];

int build(int l, int r) {
    if (l == r) {
        cur ++;
        return cur;
    }

    int mid = (l + r) / 2;
    cur ++;
    int id = cur;
    child[id][0] = build(l, mid);
    child[id][1] = build(mid + 1, r);

    return id;
}

int update(int id, int l, int r, int p) {
    if (l == r) {
        cur ++;
        persis_st[cur] = w[p];
        //cout << p << " " << w[p] << "\n";
        return cur;
    }

    int mid = (l + r) / 2;
    cur ++;
    int new_id = cur;

    if (p <= mid) {
        child[new_id][0] = update(child[id][0], l, mid, p);
        child[new_id][1] = child[id][1];
    }

    else {
        child[new_id][0] = child[id][0];
        child[new_id][1] = update(child[id][1], mid + 1, r, p);
    }

    persis_st[new_id] = max(persis_st[child[new_id][0]], persis_st[child[new_id][1]]);

    return new_id;
}

int get_max(int id, int l, int r, int u, int v) {
    if (r < u || v < l) return 0;

    if (u <= l && r <= v) return persis_st[id];

    int mid = (l + r) / 2;
    return max(get_max(child[id][0], l, mid, u, v), get_max(child[id][1], mid + 1, r, u, v));
}

void build2(int id, int l, int r) {
    if (l == r) return;

    int mid = (l + r) / 2;
    build2(child[id][0], l, mid);
    build2(child[id][1], mid + 1, r);

    st_max_pair[id] = max(st_max_pair[child[id][0]], st_max_pair[child[id][1]]);

    int x = persis_st[child[id][0]];
    int y = get_max(ver[pos[x] - 1], 1, n, mid + 1, r);

    //cout << l << " " << r << " : " << pos[x] - 1 << " ; " << x << " " << y << "\n";

    if (y > 0) st_max_pair[id] = max(st_max_pair[id], x + y);
}

pair<int, int> get(int id, int l, int r, int u, int v) {// get wi > wj, i < j that wi + wj is max
    if (r < u || v < l) return {0, 0};

    if (u <= l && r <= v) return {st_max_pair[id], persis_st[id]};

    int mid = (l + r) / 2;
    pair<int, int> ans1 = get(child[id][0], l, mid, u, v);
    pair<int, int> ans2 = get(child[id][1],mid + 1, r, u, v);

    int ans = max(ans1.first, ans2.first);
    int y = get_max(ver[pos[ans1.second]] - 1, 1, n, mid + 1, r);
    if (y > 0) ans = max(ans, ans1.second + y);

    return {ans, max(ans1.second, ans2.second)};
}


void prep() {
    cin >> n >> q;
    vector<pair<int, int>> v;
    for (int i = 1; i <= n; i ++) {
        cin >> w[i];
        w[i] ++;
        v.push_back({w[i], i});
    }
    sort(v.begin(), v.end());
    ver[0] = build(1, n);

    ver[1] = update(ver[0], 1, n, v[0].second);
    pos[v[0].first] = 1;
    for (int i = 1; i < n; i ++) {
        pos[v[i].first] = pos[v[i - 1].first];
        if (v[i].first > v[i - 1].first) pos[v[i].first] ++;
        ver[pos[v[i].first]] = update(ver[pos[v[i - 1].first]], 1, n, v[i].second);
        //cout << persis_st[ver[pos[v[i].first]]] << " " << get_max(ver[pos[v[i].first]],1 , n, 1, n) << "\n";
    }
    m = pos[v[n - 1].first];

    build2(ver[m], 1, n);
    //cout << m << "\n";


}

void solve() {
    int l, r, k;
    while (q --) {
        cin >> l >> r >> k;
        pair<int, int> ans = get(ver[m], 1, n, l, r);
        //cout << ans.first << " " << ans.second << "\n";
        if (ans.first == 0 || ans.first <= k + 2) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
    //cout << get(ver[m], 1, n, 1, n).first;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    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