Submission #1095044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095044		RiverFlow	Sequence (APIO23_sequence)	C++17	11 / 100	299 ms	9552 KiB

sequence

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)5e5 + 7;

int n, a[N];

namespace SUB1 {
struct CTDL {
    multiset<int> a, b;
    void add(int x) {
        if (sz(a) <= sz(b)) a.insert(x);
        else b.insert(x);
        if (sz(a) and sz(b) and *a.rbegin()>*b.begin()){
            int x=*a.rbegin(), y=*b.begin();
            a.erase(a.find(x));
            b.erase(b.find(y));
            a.insert(y);
            b.insert(x);
        }
    }
    void del(int x) {
        if (a.find(x) != a.end()) {
            a.erase(a.find(x));
        } else
            b.erase(b.find(x));
        if (sz(a) < sz(b)) {
            a.insert(*b.begin());
            b.erase(b.find(*b.begin()));
        } else if (sz(a) == sz(b) + 2) {
            int t = *a.rbegin();
            a.erase(a.find(t));
            b.insert(t);
        }
    }
    int med() {
        return *a.rbegin();
    }
};

int sol() {
    int ans = 0;
    vec<int> cnt(n + 1, 0);
    FOR(i, 1, n) {
        CTDL s;
        FOR(j, i, n) {
            ++cnt[a[j]];
            s.add(a[j]);
            ans = max(ans, cnt[s.med()]);
        }
        FOR(j, i, n) {
            --cnt[a[j]];
        }
    }
    return ans;
}
};

int sequence(int N, vector<int> A) {
    n = N;
    FOR(i, 1, n) a[i] = A[i - 1];
    if (n <= 2000) {
        return SUB1::sol();
    }
    return 0;
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    int n; cin >> n;
    vector<int> a(n);
    for(int & x : a) cin >> x;
    cout << sequence(n, a);
}
#endif LOCAL

Compilation message (stderr)

sequence.cpp:103:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  103 | #endif LOCAL
      |        ^~~~~

• Subtask 1: 11 / 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