Submission #1131673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131673		antonn	Sequence (APIO23_sequence)	C++20	40 / 100	2095 ms	43332 KiB

sequence

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 5e5+7;

int n, a[N];
vector<int> occ[N];
int pref[N];
int min_pref[N], max_pref[N];
int min_suff[N], max_suff[N];

bool intersect(pair<int, int> a, pair<int, int> b) {
    if (a.second < b.first || a.first > b.second) return false;
    return true;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        if (occ[i].empty()) continue;
        for (int j = 1; j <= n; ++j) pref[j] = 0;
        for (int j = 1; j <= n; ++j) {
            if (a[j] < i) pref[j] = -1;
            if (a[j] > i) pref[j] = 1;
        }
        for (int j = 1; j <= n; ++j) pref[j] += pref[j - 1];
        
        min_suff[n + 1] = 1e9, max_suff[n + 1] = -1e9;
        for (int j = 1; j <= n; ++j) min_pref[j] = min(min_pref[j - 1], pref[j]);
        for (int j = 1; j <= n; ++j) max_pref[j] = max(max_pref[j - 1], pref[j]);
        for (int j = n; j >= 1; --j) min_suff[j] = min(min_suff[j + 1], pref[j]);
        for (int j = n; j >= 1; --j) max_suff[j] = max(max_suff[j + 1], pref[j]);
        
        for (int j = 0; j + x - 1 < occ[i].size(); ++j) {
            int l = occ[i][j];
            int r = occ[i][j + x - 1];
            pair<int, int> lft = {min_pref[l - 1], max_pref[l - 1]};
            pair<int, int> rgh = {min_suff[r] - x, max_suff[r] + x};
            if (intersect(lft, rgh)) {
                return true;
            }
        }
    }
    return false;
}

int sequence(int N, vector<int> A) {
    n = N;
    for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
    for (int i = 1; i <= n; ++i) occ[a[i]].push_back(i);
    
    int l = 1, r = n;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return l - 1;
}

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