Submission #1228317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228317		Dzadzo	Sequence (APIO23_sequence)	C++20	82 / 100	2096 ms	80544 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
#define ll long long
// #define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 200000
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")



struct LazySegTree {
    struct Node { int mn, mx, add; Node(): mn(INT_MAX), mx(INT_MIN), add(0) {} };
    int n;
    vector<Node> st;

    LazySegTree(int _n): n(_n) { st.resize(4*(n+1)); }

    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) { st[p].mn = st[p].mx = a[l]; return; }
        int m = (l + r) >> 1;
        build(p<<1, l, m, a);
        build(p<<1|1, m+1, r, a);
        pull(p);
    }

    void pull(int p) {
        st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
        st[p].mx = max(st[p<<1].mx, st[p<<1|1].mx);
    }

    void apply(int p, int v) {
        st[p].mn += v;
        st[p].mx += v;
        st[p].add += v;
    }

    void push(int p) {
        if (st[p].add) {
            apply(p<<1, st[p].add);
            apply(p<<1|1, st[p].add);
            st[p].add = 0;
        }
    }

    void update(int p, int l, int r, int i, int j, int v) {
        if (j < l || r < i) return;
        if (i <= l && r <= j) { apply(p, v); return; }
        push(p);
        int m = (l + r) >> 1;
        update(p<<1, l, m, i, j, v);
        update(p<<1|1, m+1, r, i, j, v);
        pull(p);
    }

    int queryMin(int p, int l, int r, int i, int j) {
        if (j < l || r < i) return INT_MAX;
        if (i <= l && r <= j) return st[p].mn;
        push(p);
        int m = (l + r) >> 1;
        return min({queryMin(p<<1, l, m, i, j), queryMin(p<<1|1, m+1, r, i, j)});
    }

    int queryMax(int p, int l, int r, int i, int j) {
        if (j < l || r < i) return INT_MIN;
        if (i <= l && r <= j) return st[p].mx;
        push(p);
        int m = (l + r) >> 1;
        return max({queryMax(p<<1, l, m, i, j), queryMax(p<<1|1, m+1, r, i, j)});
    }

    void build(const vector<int>& a) { build(1, 1, n, a); }
    void Add(int l, int r, int v) { update(1, 1, n, l, r, v); }
    int Min(int l, int r) { return queryMin(1, 1, n, l, r); }
    int Max(int l, int r) { return queryMax(1, 1, n, l, r); }
};


int sequence(int n, vi a) {
    vvi Q(n+1);
    reverse(a.begin(), a.end());
    a.pb(0);
    reverse(a.begin(), a.end());
    for (int i=1;i<=n;i++)Q[a[i]].pb(i);


    LazySegTree pmax(n),pmin(n);


    pmax.build(vi(n+1,0));
    pmin.build(vi(n+1,0));

    for (int i=1;i<=n;i++)pmin.Add(i,n,1),pmax.Add(i,n,1);
    int res=1;
    for (int i=1;i<=n;i++) {

        for (int x:Q[i]) {
            pmax.Add(x,n,-1);
            pmin.Add(x,n,-1);
        }

        vi prefmin(Q[i].size()),prefmax(Q[i].size()),suffmin(Q[i].size()),suffmax(Q[i].size());

        for (int j=0;j<Q[i].size();j++) {
            int idx=Q[i][j];

            if (idx>1) {
                prefmin[j]=pmin.Min(1,idx-1);
                prefmax[j]=pmax.Max(1,idx-1);
            }
            // for (int z=1;z<=n;z++)cout<<pmax.Max(z,z)<<" ";cout<<'\n';
            // for (int z=1;z<=n;z++)cout<<pmin.Max(z,z)<<" ";cout<<'\n';
            // cout<<'\n';
            pmin.Add(1,idx,-1);
            pmax.Add(1,idx,1);


            prefmax[j]=max(prefmax[j],0);
            prefmin[j]=min(prefmin[j],0);

        }

        for (int j=0;j<Q[i].size();j++) {

            int idx=Q[i][j];

            pmin.Add(1,idx,1);
            pmax.Add(1,idx,-1);
        }

        for (int j=Q[i].size()-1;j>=0;j--) {

            int idx=Q[i][j];

            suffmin[j]=pmin.Min(idx,n);
            suffmax[j]=pmax.Max(idx,n);

            pmin.Add(idx,n,-1);
            pmax.Add(idx,n,1);

        }

        for (int j=Q[i].size()-1;j>=0;j--) {

            int idx=Q[i][j];
            pmin.Add(idx,n,1);
            pmax.Add(idx,n,-1);

        }


        int L=0;
        // cout<<i<<"---------------\n";
        // for (int i=1;i<=n;i++) {
        //     cout<<pmin.Max(i,i)<<" ";
        // }
        // cout<<'\n';

        for (int R=0;R<Q[i].size();R++) {
            // cout<<prefmin[R]<<" "<<prefmax[R]<<'\n';
            // cout<<suffmin[R]<<" "<<suffmax[R]<<'\n';
            while (L < R  && ( suffmax[R]-prefmin[L] < - ( R - L + 1 ) || suffmin[R]-prefmax[L] > ( R - L + 1 ) )  )L++;
            // cout<<L<<" "<<R<<'\n';
            // cout<<'\n';
            res=max(res,R-L+1);

        }

        for (int x:Q[i])pmin.Add(x,n,-1),pmax.Add(x,n,-1);
    }
    return res;

}

//
// int sequence1(int N, const vector<int>& A) {
//     int ans = 0;
//     // Enumerate all subarrays [l..r]
//     for (int l = 0; l < N; ++l) {
//         for (int r = l; r < N; ++r) {
//             // Extract and sort the subarray A[l..r]
//             vector<int> B;
//             B.reserve(r - l + 1);
//             for (int i = l; i <= r; ++i)
//                 B.push_back(A[i]);
//             sort(B.begin(), B.end());              // O(k log k), k = r-l+1
//
//             int k = B.size();
//             // Find the median set S
//             vector<int> medians;
//             if (k % 2 == 1) {
//                 medians.push_back(B[k/2]);
//             } else {
//                 medians.push_back(B[k/2 - 1]);
//                 medians.push_back(B[k/2]);
//             }
//
//             // For each median x, count W(l,r,x) by scanning A[l..r]
//             for (int x : medians) {
//                 int cnt = 0;
//                 for (int i = l; i <= r; ++i)
//                     if (A[i] == x) ++cnt;
//                 ans = max(ans, cnt);
//             }
//         }
//     }
//     return ans;
// }
// int main() {
//      int n=8;
//     vi a={1,3,4,3,5,6,8,3};
//     cout<<sequence(n,a)<<endl;
//     // for (int i=0;i<n;i++)a.pb(1);
//     // while (sequence(n,a)==sequence1(n,a)) {
//     //     cout<<"valid\n";
//     //     for (int i=0;i<n;i++)a[i]=rand()%n+1;
//     // }
//     // for (int x:a)cout<<x<<" ";
// }
/*



*/

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