Submission #1328771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328771		nguyenkhangninh99	Sequence (APIO23_sequence)	C++20	28 / 100	2096 ms	43552 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

int sequence(int n, vector<int> c){
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) a[i] = c[i - 1];

    vector<vector<int>> pos(n + 1);
    for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
    
    vector<int> pre(n + 1);
    int ans = 1;
    for(int val = 1; val <= n; val++){
        for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (a[i] > val) - (a[i] < val);
        
        vector<int> premn(n + 2), premx(n + 2);
        for(int i = 1; i <= n; i++){
            premn[i] = min(premn[i - 1], pre[i]);
            premx[i] = max(premx[i - 1], pre[i]);
        }
        vector<int> sufmn(n + 2), sufmx(n + 2);
        sufmn[n + 1] = 1e9, sufmx[n + 1] = -1e9;
        for(int i = n; i >= 1; i--){
            sufmn[i] = min(sufmn[i + 1], pre[i]);
            sufmx[i] = max(sufmx[i + 1], pre[i]);
        }
        for(int i = 0; i < pos[val].size(); i++){
            for(int j = i + 1; j < pos[val].size(); j++){
                if(max(premn[pos[val][i] - 1] - sufmx[pos[val][j]], sufmn[pos[val][j]] - premx[pos[val][i] - 1]) <= j - i + 1) ans = max(ans, j - i + 1);
            }
        }
    }

    return ans;
}
#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    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:47:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
   47 | #endif LOCAL
      |        ^~~~~

• 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