Submission #1095109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095109		RiverFlow	Sequence (APIO23_sequence)	C++17	48 / 100	621 ms	102488 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 or a == -1) { 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);
        }
    }
    int med() {
        return *a.rbegin();
    }
    int med2() {
        return *b.begin();
    }
};

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()]);
            if ( (j - i + 1) % 2 == 0 )
                ans = max(ans, cnt[s.med2()]);
        }
        FOR(j, i, n) {
            --cnt[a[j]];
        }
    }
    return ans;
}
};

namespace SUB2 {
bool check() {
    vec<bool> okl(n + 1, 0), okr(n + 1, 0);
    okl[1] = 1;
    FOR(i, 2, n) {
        okl[i] = okl[i - 1] and (a[i] >= a[i-1]);
    }
    okr[n] = 1;
    FOD(i, n - 1, 1) {
        okr[i] = okr[i + 1] and (a[i] >= a[i + 1]);
    }
    FOR(i, 1, n) {
        if (okl[i] and okr[i])
            return 1;
    }
    return 0;
}
int sol() {
    int ans = 0;
    vec<int> cnt(n + 1, 0);
    vec<ii> b;
    FOR(i, 1, n) {
        int j = i;
        while (j + 1 <= n and a[j + 1] == a[i])
            ++j;
        b.push_back(_mp(a[i], j - i + 1));
        cnt[a[i]] += j - i + 1;
        ans = max(ans, j - i + 1);
        i = j;
    }
    sort(all(b));
    int g = 0;
    for(int i = sz(b) - 1; i >= 0; --i) {
        ii j = b[i];
        int v = j.fi, c = j.se;
        if (c!=cnt[v]) {
            int k=g;
            int p=cnt[v];
            int j=n-(k+p);
            if (j >= k - p) {
                ans = max(ans, cnt[v]);
            }
//            cerr << v << ' ' << k << ' ' << p << ' ' << j << nl;
        }
        g+=cnt[v];
        if (i > 0 and b[i].fi==b[i-1].fi)
            --i;
    }
    return ans;
}
};

struct IT {
    int n;
    vec<ii> t;
    vec<int> lz;
    IT (){};
    IT (int _n) {
        n = _n;
        lz.resize(4 * n + 7);
        t.resize(4 * n + 7);
    }
    vec<int> a;
    void refine(int id) {
        t[id].fi = min(t[id << 1].fi, t[id << 1 | 1].fi);
        t[id].se = max(t[id << 1].se, t[id << 1 | 1].se);
    }
    void build(int id, int l, int r) {
        if (l == r) {
            return void(t[id]=_mp(a[l], a[l]));
        }
        int m = (l + r) >> 1;
        build(id << 1, l, m);
        build(id << 1 | 1, m + 1, r);
        refine(id);
    }
    void init(vec<int> p){
        a.resize(n + 1);
        FOR(i, 1, n) a[i] = p[i];
        build(1, 1, n);
    }
    void push(int id) {
        int &x = lz[id];
        t[id<<1].fi+=x;
        t[id<<1|1].fi+=x;
        t[id<<1].se+=x;
        t[id<<1|1].se+=x;
        lz[id<<1]+=x;
        lz[id<<1|1]+=x;
        x=0;
    }
    void update(int id, int l, int r, int u, int v, int val) {
        if (l > v or r < u) return ;
        if (l >= u and r <= v) {
            t[id].fi += val;
            t[id].se += val;
            lz[id] += val;
            return ;
        }
        if (lz[id]) {
            push(id);
        }
        int m = (l + r) >> 1;
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);
        refine(id);
    }
    void update(int l, int r, int v) {
        if (l > r) return ;
        update(1, 1, n, l, r, v);
    }
    ii get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) {
            return _mp(n, -n);
        }
        if (l >= u and r <= v)
            return t[id];
        if (lz[id]) {
            push(id);
        }
        int m = (l + r) >> 1;
        ii A = get(id << 1, l, m, u, v);
        ii B = get(id << 1 | 1, m + 1, r, u, v);
        return _mp(min(A.fi, B.fi), max(A.se, B.se));
    }
    ii get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};
vec<int> pos[N];

namespace SUB5 {
bool check() {
    vec<int> cnt(n + 1, 0);
    FOR(i, 1, n) ++cnt[a[i]];
    if (*max_element(all(cnt)) > 2)
        return 0;
    return 1;
}
int sol() {
    FOR(i, 1, n - 1) if (a[i] == a[i+1])
        return 2;
    int ans = 1;
    FOR(i, 1, n) {
        pos[a[i]].push_back(i);
    }
    IT st1(n), st2(n);
    vec<int> p(n+1,0);
    FOR(i,1,n)p[i]=-(i-1);
    st1.init(p); // pref(l-1)
    FOR(i,1,n)p[i]=-i;
    st2.init(p); // pref(r)

    FOR(i, 1, n) if (sz(pos[i])) {
        if (sz(pos[i]) == 2) {
            int x = pos[i][0], y = pos[i][1];
            ii A = st1.get(1,x);
            assert(A.fi <= A.se);
//            cerr << A.fi << ' ' << A.se<< nl;
            A.fi-=4;
            ii B = st2.get(y,n);
//            cerr << B.fi << ' ' << B.se << nl;
//            cerr << x << ' ' << y << nl;
            if (!(A.fi > B.se or A.se < B.fi)) {
                ans=2;
                return ans;
            }
        }
        for(int j : pos[i]) {
            //pref(j+1) duoc cong them 2
            st1.update(j + 1, n, 2);
            st2.update(j, n, 2);
        }
    }
    return 1;
}
};

struct segment_tree {
    int n;
    vector<int> t, lz;
    segment_tree () {};
    segment_tree (int _n) {
        n = _n;
        t.assign(4 * n + 7, n + 1);
        lz.assign(4 * n + 7, -1);
    }
    void push(int id) {
        int &x = lz[id];
        mini(t[id << 1], x);
        mini(t[id << 1 | 1], x);
        mini(lz[id << 1], x);
        mini(lz[id << 1 | 1], x);
        x = -1;
    }
    void upd(int id, int l, int r, int u, int v, int val) {
        if (l > v or r < u) return ;
        t[id] = min(t[id], val);
        if (l >= u and r <= v) {
            mini(lz[id], val);
            return ;
        }
        if (lz[id] != -1) {
            push(id);
        }
        int m = (l + r) >> 1;
        upd(id << 1, l, m, u, v, val);
        upd(id << 1 | 1, m + 1, r, u, v, val);
    }
    void upd(int l, int r, int val) {
        upd(1, 1, n, l, r, val);
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return n;
        if (l >= u and r <= v) return t[id];
        int m = (l + r) >> 1;
        if (lz[id] != -1) {
            push(id);
        }
        return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }
    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

ii A[N], B[N];

namespace SUB_FULL {
int sol() {
    int ans = 1;
    FOR(i, 1, n) {
        pos[a[i]].push_back(i);
    }
    IT st1(n), st2(n);
    vec<int> p(n+1,0);
    FOR(i,1,n)p[i]=-(i-1);
    st1.init(p); // pref(l-1)
    FOR(i,1,n)p[i]=-i;
    st2.init(p); // pref(r)

    FOR(i, 1, n) if (sz(pos[i])) {
        if (sz(pos[i]) > 1) {
            vec<int> &c = pos[i];
            for(int j = 0; j < sz(c); ++j) {
                A[j] = st1.get(1, c[j]);
                B[j] = st2.get(c[j], n);
            }
            vec<int> cord;
            auto key = [&](int val) -> int {
                return lower_bound(all(cord), val) - cord.begin() + 1;
            };
            for(int j = 0; j < sz(c); ++j) {
                cord.push_back(A[j].fi + 2 * j - 2);
                cord.push_back(A[j].second);
                cord.push_back(B[j].se + 2 * j);
                cord.push_back(B[j].fi);
            }
            unq(cord);
            segment_tree st(sz(cord));
            for(int j = 0; j < sz(c); ++j) {
                if (j > 0) {
                    int L = key(B[j].fi);
                    int R = key(B[j].se + 2 * j);
//                    cerr << j << ' ' << st.get(L, R) << nl;
                    ans = max(ans, j - st.get(L, R) + 1);
                }
                int L = key(A[j].fi + 2 * j - 2);
                int R = max(L, key(A[j].se));
                st.upd(L, R, j);
            }
        }
        for(int j : pos[i]) {
            //pref(j+1) duoc cong them 2
            st1.update(j + 1, n, 2);
            st2.update(j, n, 2);
        }
    }
    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();
    }
    if (SUB2::check()) {
        return SUB2::sol();
    }
    if (SUB5::check()) {
        return SUB5::sol();
    }
    return SUB_FULL::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:382:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  382 | #endif LOCAL
      |        ^~~~~

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