Submission #1131699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131699		antonn	Sequence (APIO23_sequence)	C++20	0 / 100	2097 ms	57156 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];

struct ST {
    int n;
    vector<pair<int, int>> t;
    vector<int> lazy;
    
    ST(int nn) {
        n = nn;
        t.assign(4 * n + 5, {0, 0});
        lazy.assign(4 * n + 5, 0);
    }
    
    pair<int, int> join(pair<int, int> a, pair<int, int> b) {
        pair<int, int> c;
        c.first = min(a.first, b.first);
        c.second = max(a.second, b.second);
        return c;
    }
    
    void push(int v, int tl, int tr) {
        if (tl < tr) {
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
        }
        t[v].first += lazy[v];
        t[v].second += lazy[v];
        lazy[v] = 0;
    }
    
    void add(int v, int tl, int tr, int l, int r, int x) {
        push(v, tl, tr);
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) {
            lazy[v] += x, push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        add(2 * v, tl, tm, l, r, x);
        add(2 * v + 1, tm + 1, tr, l, r, x);
        t[v] = join(t[2 * v], t[2 * v + 1]);
    }
    
    void add(int l, int r, int x) {
        add(1, 1, n + 1, l + 1, r + 1, x);
    }
    
    pair<int, int> get(int v, int tl, int tr, int l, int r) {
        push(v, tl, tr);
        if (l > tr || r < tl) return {1e9, -1e9};
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2;
        return join(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
    }
    
    int get_min(int l, int r) {
        return get(1, 1, n, l+1, r+1).first;
    }
    
    int get_max(int l, int r) {
        return get(1, 1, n, l+1, r+1).second;
    }
};

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) {
    ST t(n);
    for (int i = 1; i <= n; ++i) t.add(i, n, 1);
    for (int i = 1; i <= n; ++i) {
        if (occ[i].empty()) continue;
        for (auto j : occ[i]) t.add(j, n, -1);
        
        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 = {t.get_min(0, l - 1), t.get_max(0, l - 1)};
            pair<int, int> rgh = {t.get_min(r, n) - x, t.get_max(r, n) + x};
            if (intersect(lft, rgh)) {
                return true;
            }
        }
        
        for (auto j : occ[i]) t.add(j, n, -1);
    }
    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: 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