oj.uz

Submission #971908

# Submission time Handle Problem Language Result Execution time Memory
971908 2024-04-29T13:12:26 Z isirazeev Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 138860 KB 
#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;
    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;
    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;
    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;
    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++) {
        cin >> a[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), l1, l2, 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 t1 = 0; t1 < 2; t1++) {
                    if (t1 == 0) L = l_min[L];
                    else L = l_max[L];
                    for (int t2 = 0; t2 < 2; t2++) {
                        if (t2 == 0) R = r_min[R];
                        else R = r_max[R];
                        dif = get_sum(1, 0, n - 1, L, R), l1, l2, sum = R - L + 1 - m;
                        l1 = (sum + dif) / 2, l2 = (sum - dif) / 2;
                        if ((L + R) / 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;
    }
    return l;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:120:63: warning: right operand of comma operator has no effect [-Wunused-value]
  120 |                         dif = get_sum(1, 0, n - 1, L, R), l1, l2, sum = R - L + 1 - m;
      |                                                               ^~
sequence.cpp:120:85: warning: right operand of comma operator has no effect [-Wunused-value]
  120 |                         dif = get_sum(1, 0, n - 1, L, R), l1, l2, sum = R - L + 1 - m;
      |                                                                                     ^

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Incorrect 2 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Incorrect 2 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Execution timed out 2024 ms 110236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Execution timed out 2024 ms 60628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 138860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Incorrect 2 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Incorrect 2 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -