Submission #760462

#	Time	Username	Problem	Language	Result	Execution time	Memory
760462		wiwiho	Sequence (APIO23_sequence)	C++17	28 / 100	2077 ms	33496 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>

using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

#define lc 2 * id
#define rc 2 * id + 1

int n;

int sequence(int N, vector<int> A){
    n = N;

    vector<vector<int>> pos(n + 1);
    for(int i = 0; i < n; i++){
        pos[A[i]].pb(i);
    }

    int ans = 0;
    for(int v = 1; v <= n; v++){
        vector<int> sum(n);
        {
            int now = 0;
            for(int j = 0; j < n; j++){
                if(A[j] < v) now--;
                else if(A[j] > v) now++;
                sum[j] = now;
            }
        }
        
        vector<pair<pii, int>> ev;

        int lst = -1;
        for(int i = 0; i < SZ(pos[v]); i++){
            int j = pos[v][i];
            int nxt = i + 1 == SZ(pos[v]) ? n : pos[v][i + 1];
            {
                int mn = sum[j], mx = sum[j];
                for(int t = lst + 1; t <= j; t++){
                    mn = min(mn, sum[t]);
                    mx = max(mx, sum[t]);
                }
                int x = i - mx, y = i + mn;
                ev.pb(mp(mp(x, y), i));
            }
            {
                int mn = sum[j], mx = sum[j];
                for(int t = j; t < nxt; t++){
                    mn = min(mn, sum[t]);
                    mx = max(mx, sum[t]);
                }
                int x = i - mn + 1, y = i + mx + 1;
                for(auto [c, id] : ev){
                    if(c.ff <= x && c.ss <= y){
                        ans = max(ans, i - id + 1);
                    }
                }
            }
            lst = j;
        }
    }


    return ans;
}

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