Submission #1273008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273008		pvpro	Sequence (APIO23_sequence)	C++20	28 / 100	2099 ms	62044 KiB

sequence

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ushort = unsigned short;

#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;

template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
    for (auto &x : v) {
        in >> x;
    }
    return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
    for (auto &x : v) {
        out << x << " ";
    }
    return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x -= delta;
    }
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x += delta;
    }
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int MAX_N = (1<<19);

struct Node {
    int mn, mx, sm;
    Node() {
        mn = 0;
        mx = 0;
        sm = 0;
    };
};

Node T[MAX_N * 2];

void merge(int i) {
    T[i].mn = min(T[i * 2].mn, T[i * 2].sm + T[i * 2 + 1].mn);
    T[i].mx = max(T[i * 2].mx, T[i * 2].sm + T[i * 2 + 1].mx);
    T[i].sm = T[i * 2].sm + T[i * 2 + 1].sm;
}

void update(int i, int x) {
    i += MAX_N;
    T[i].sm = x;
    T[i].mn = min(x, 0);
    T[i].mx = max(x, 0);
    i /= 2;
    while (i) {
        merge(i);
        i /= 2;
    }
}

Node get(int i, int l, int r, int ql, int qr) {
    if (l >= qr) {
        return T[0];
    }
    if (r <= ql) {
        return T[i];
    }
    if (ql <= l && r <= qr) {
        return T[i];
    } else {
        int m = (l + r) / 2;
        Node a = get(i * 2, l, m, ql, qr);
        Node b = get(i * 2 + 1, m, r, ql, qr);
        if (m > ql) {
            b.mn = min(a.mn, a.sm + b.mn);
            b.mx = max(a.mx, a.sm + b.mx);
        } else {
            b.mn = a.sm + b.mn;
            b.mx = a.sm + b.mx;
        }
        b.sm = a.sm + b.sm;
        return b;
    }
}

int F[MAX_N * 4];

void updateF(int i) {
    i += MAX_N * 2;
    F[i] = 1e9;
    i /= 2;
    while (i) {
        F[i] = 1e9;
        i /= 2;
    }
}

void updateF(int i, int x) {
    i += MAX_N * 2;
    F[i] = min(F[i], x);
    i /= 2;
    while (i) {
        F[i] = min(F[i * 2], F[i * 2 + 1]);
        i /= 2;
    }
}

int getF(int i, int l, int r, int ql, int qr) {
    if (r <= ql || l >= qr) {
        return 1e9;
    }
    if (ql <= l && r <= qr) {
        return F[i];
    } else {
        int m = (l + r) / 2;
        return min(getF(i * 2, l, m, ql, qr), getF(i * 2 + 1, m, r, ql, qr));
    }
}

int solve(int n, vector<int> a) {
    T[0].mn = 1e9;
    T[0].mx = -1e9;
    for (int i = MAX_N * 2 - 1; i >= MAX_N; --i) {
        T[i].mn = 0;
        T[i].mx = 1;
        T[i].sm = 1;
    }
    for (int i = MAX_N - 1; i > 0; --i) {
        merge(i);
    }
    for (int i = 0; i < MAX_N * 4; ++i) {
        F[i] = 1e9;
    }
    vector<vector<int>> p(n + 1);
    for (int i = 0; i < n; ++i) {
        p[a[i]].pb(i);
    }
    int ans = 1;
    vector<int> td;
    vector<pii> L;
    td.reserve(n * 2);
    L.resize(n * 2);
    for (int x = 1; x <= n; ++x) {
        if (p[x].size() > ans) {
            for (auto &y: p[x]) {
                update(y, 0);
            }
            for (int q = 0; q <= p[x].size(); ++q) {
                int l = 0, r = n;
                if (q != p[x].size()) {
                    r = p[x][q] + 1;
                }
                if (q != 0) {
                    l = p[x][q - 1];
                }
                Node a = get(1, 0, MAX_N, l, r);
                L[q] = mp(a.mn, a.mx);
            }
            auto check = [&](int nans) {
                while (!td.empty()) {
                    updateF(td.back());
                    td.pop_back();
                }
                for (int i = 1; i < MAX_N * 4; ++i) {
                    assert(F[i] == 1e9);
                }
                for (int q = 0; q <= p[x].size(); ++q) {
                    if (q >= nans) {
                        updateF(L[q - nans].f - (q - nans) + MAX_N, L[q - nans].f + (q - nans));
                        updateF(L[q - nans].s - (q - nans) + MAX_N, L[q - nans].s + (q - nans));
                        td.pb(L[q - nans].f - (q - nans) + MAX_N);
                        td.pb(L[q - nans].s - (q - nans) + MAX_N);
                    }
                    if (getF(1, 0, MAX_N * 2, L[q].f - q + MAX_N, MAX_N * 2) <= L[q].s + q) {
                        return true;
                    }
                }
                return false;
            };
            int lg = 0;
            while (check(ans + (1<<lg))) {
                ++lg;
            }
            if (lg > 0) {
                ans += (1 << (lg - 1));
                while (--lg) {
                    if (check(ans + (1 << (lg - 1)))) {
                        ans += (1 << (lg - 1));
                    }
                }
            }
        }
        for (auto &y : p[x]) {
            update(y, -1);
        }
    }
    return ans;
}

int sequence(int n, vector<int> a) {
    int ans = solve(n, a);
    reverse(all(a));
    ans = min(ans, solve(n, a));
    return ans;
}

#ifdef LOCAL
int main() {
    freopen("in.txt", "r", stdin);
    int N;
    assert(1 == scanf("%d", &N));

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &A[i]));
    }

    int result = sequence(N, A);
    printf("%d\n", result);
    return 0;
}
#endif

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