Submission #972177

#	Time	Username	Problem	Language	Result	Execution time	Memory
972177		isirazeev	Sequence (APIO23_sequence)	C++17	0 / 100	2101 ms	133360 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 * 5 + 10;

int t[4 * N];
pair<int, int> pref_max[4 * N], pref_min[4 * N], suf_max[4 * N], suf_min[4 * N];
int n;

void update(int v, int l, int r, int pos, int val) {
    if (l == r) {
        t[v] = val;
        pref_max[v] = {max(0, val), (val >= 0 ? l : -1)}, pref_min[v] = {min(0, val), (val <= 0 ? l : -1)};
        suf_max[v] = {max(0, val), (val >= 0 ? l : n)}, suf_min[v] = {min(0, val), (val <= 0 ? l : n)};
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(v * 2, l, mid, pos, val);
    else update(v * 2 + 1, mid + 1, r, pos, val);
    t[v] = t[v * 2] + t[v * 2 + 1];
    pref_max[v] = max(pref_max[v * 2], {t[v * 2] + pref_max[v * 2 + 1].first, pref_max[v * 2 + 1].second});
    pref_min[v] = min(pref_min[v * 2], {t[v * 2] + pref_min[v * 2 + 1].first, pref_min[v * 2 + 1].second});
    suf_max[v] = max(suf_max[v * 2 + 1], {t[v * 2 + 1] + suf_max[v * 2].first, suf_max[v * 2].second});
    suf_min[v] = min(suf_min[v * 2 + 1], {t[v * 2 + 1] + suf_min[v * 2].first, suf_min[v * 2].second});
}

pair<int, int> get_max_pref(int v, int l, int r, int p) {
    if (l > p)
        return {-(int) 1e9, -1};
    if (r <= p)
        return pref_max[v];
    int mid = (l + r) / 2;
    if(mid >= p) return get_max_pref(v * 2, l, mid, p);
    auto pr = get_max_pref(v * 2 + 1, mid + 1, r, p);
    return max(get_max_pref(v * 2, l, mid, p), {t[v * 2] + pr.first, pr.second});
}

pair<int, int> get_min_pref(int v, int l, int r, int p) {
    if (l > p)
        return {(int) 1e9, -1};
    if (r <= p)
        return pref_min[v];
    int mid = (l + r) / 2;
    if(mid >= p) return get_min_pref(v * 2, l, mid, p);
    auto pr = get_min_pref(v * 2 + 1, mid + 1, r, p);
    return min(get_min_pref(v * 2, l, mid, p), {t[v * 2] + pr.first, pr.second});
}

pair<int, int> get_max_suf(int v, int l, int r, int p) {
    if (r < p)
        return {-(int) 1e9, -1};
    if (l >= p)
        return suf_max[v];
    int mid = (l + r) / 2;
    if (mid < p) return get_max_suf(v * 2 + 1, mid + 1, r, p);
    auto pr = get_max_suf(v * 2, l, mid, p);
    return max(get_max_suf(v * 2 + 1, mid + 1, r, p), {t[v * 2 + 1] + pr.first, pr.second});
}

pair<int, int> get_min_suf(int v, int l, int r, int p) {
    if (r < p)
        return {(int) 1e9, -1};
    if (l >= p)
        return suf_min[v];
    int mid = (l + r) / 2;
    if (mid < p) return get_min_suf(v * 2 + 1, mid + 1, r, p);
    auto pr = get_min_suf(v * 2, l, mid, p);
    return min(get_min_suf(v * 2 + 1, mid + 1, r, p), {t[v * 2 + 1] + pr.first, pr.second});
}

int get_sum(int v, int l, int r, int tl, int tr) {
    if (l > tr || r < tl) return 0;
    if (l >= tl && r <= tr)
        return t[v];
    int mid = (l + r) / 2;
    return get_sum(v * 2, l, mid, tl, tr) + get_sum(v * 2 + 1, mid + 1, r, tl, tr);
}

int sequence(int nn, vector<int> a) {
    n = nn;
    set<int, greater<>> val;
    map<int, vector<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[a[i]].emplace_back(i);
        val.insert(a[i]);
    }
    int l_max[n], l_min[n], r_max[n], r_min[n];
    for (int i = 0; i < n; i++) update(1, 0, n - 1, i, 1);
    for (int x: val) {
        for (int i: pos[x]) update(1, 0, n - 1, i, 0);
        for (int i: pos[x]) {
            auto p1 = get_min_pref(1, 0, n - 1, i), p2 = get_max_pref(1, 0, n - 1, i);
            auto s1 = get_min_suf(1, 0, n - 1, i), s2 = get_max_suf(1, 0, n - 1, i);
            l_max[i] = min(i, p1.second + 1);
            l_min[i] = min(i, p2.second + 1);
            r_max[i] = max(i, s1.second - 1);
            r_min[i] = max(i, s2.second - 1);
        }
        for (int i: pos[x]) update(1, 0, n - 1, i, -1);
    }
    int l = 0, r = n + 1;
    while (r - l > 1) {
        int m = (l + r) / 2, C = 0;
        for (int i = 0; i < n; i++) update(1, 0, n - 1, i, 1);
        for (int x: val) {
            for (int i: pos[x]) update(1, 0, n - 1, i, 0);
            for (int i = 0; i + m - 1 < (int) pos[x].size(); i++) {
                int L = pos[x][i], R = pos[x][i + m - 1];
                int dif = get_sum(1, 0, n - 1, L, R), sum = R - L + 1 - m;
                int l1 = (sum + dif) / 2, l2 = (sum - dif) / 2;
                int LL = L, RR = R;
                for (int t1 = 0; t1 < 2; t1++) {
                    if (t1 == 0) L = l_min[LL];
                    else L = l_max[LL];
                    for (int t2 = 0; t2 < 2; t2++) {
                        if (t2 == 0) R = r_min[RR];
                        else R = r_max[RR];
                        dif = get_sum(1, 0, n - 1, L, R), sum = R - L + 1 - m;
                        l1 = (sum + dif) / 2, l2 = (sum - dif) / 2;
                        if (((L + R) / 2 >= L + l1 && (L + R) / 2 <= R - l2)
                            || ((L + R + 1) / 2 >= L + l1 && (L + R + 1) / 2 <= R - l2)) {
                            C = 1;
                            break;
                        }
                    }
                }
            }
            for (int i: pos[x]) update(1, 0, n - 1, i, -1);
        }
        if (C == 1) l = m;
        else r = m;
    }
    if(l == 18) exit(-1);
    return l;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18