Submission #1144179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144179		vladilius	Sequence (APIO23_sequence)	C++20	28 / 100	2097 ms	33436 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    vector<int> a;
    int n;
    ST(int ns){
        n = ns;
        a.resize(n + 1);
    }
    void add(int l, int r, int x){
        for (int i = l; i <= r; i++){
            a[i] += x;
        }
    }
    pii get(int l, int r){
        pii out = {1e9, -1e9};
        for (int i = l; i <= r; i++){
            out.ff = min(out.ff, a[i]);
            out.ss = max(out.ss, a[i]);
        }
        return out;
    }
};

int sequence(int n, vector<int> a){
    a.insert(a.begin(), 0);
    vector<int> d[n + 1];
    for (int i = 1; i <= n; i++) d[a[i]].pb(i);
    
    ST T(n);
    for (int i = 1; i <= n; i++) T.add(i, n, 1);
    
    int out = 1;
    for (int x = 1; x <= n; x++){
        if (d[x].empty()) continue;
        for (int j: d[x]) T.add(j, n, -1); // a[j] = 0
        
        
        vector<pii> all;
        all.pb({0, d[x][0] - 1});
        // [0, d[x][0] - 1]
        for (int i = 0; i + 1 < d[x].size(); i++){
            all.pb({d[x][i], d[x][i + 1] - 1});
            // [d[x][i], d[x][i + 1] - 1]
        }
        all.pb({d[x].back(), n});
        // [d[x].back(), n]
        
        for (auto &[l, r]: all){
            pii f = T.get(l, r);
            l = f.ff; r = f.ss;
        }
        
        for (int i = 0; i < all.size(); i++){
            for (int j = i + 1; j < all.size(); j++){
                if (i + all[i].ff <= j + all[j].ss && i - all[i].ss <= j - all[j].ff){
                    out = max(out, j - i);
                }
            }
        }
        
        for (int j: d[x]) T.add(j, n, -1); // a[j] = -1
    }
    
    // -e <= h - l <= e
    // 0 <= i < j;
    
    // [li, ri]; [lj, rj];
    // h - l: [lj - ri, rj - li]
    // inter [i - j, j - i] is not empty
    // max(i - j, lj - ri) <= min(rj - li, j - i);
    // i - j <= rj - li <-> i + li <= rj + j
    // lj - ri <= j - i <-> i - ri <= j - lj
    
    return out;
}

• 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