Submission #1144185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144185		vladilius	Sequence (APIO23_sequence)	C++20	100 / 100	690 ms	108012 KiB

sequence

// https://codeforces.com/blog/entry/116491?#comment-1031345

#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
#define arr3 array<int, 3>

struct ST{
    vector<pii> t;
    vector<int> p;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        p.resize(4 * n);
    }
    void push(int v){
        if (!p[v]) return;
        int vv = 2 * v;
        t[vv].ff += p[v];
        t[vv].ss += p[v];
        p[vv] += p[v];
        t[vv + 1].ff += p[v];
        t[vv + 1].ss += p[v];
        p[vv + 1] += p[v];
        p[v] = 0;
    }
    pii merge(pii x, pii y){
        return {min(x.ff, y.ff), max(x.ss, y.ss)};
    }
    void add(int v, int tl, int tr, int l, int r, int x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v].ff += x;
            t[v].ss += x;
            p[v] += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
        t[v] = merge(t[vv], t[vv + 1]);
    }
    void add(int l, int r, int x){
        add(1, 1, n, l, r, x);
    }
    pii get(int v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return {1e9, -1e9};
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        return merge(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    pii get(int l, int r){
        pii out = get(1, 1, n, l + !l, r);
        if (!l){
            out.ff = min(out.ff, 0);
            out.ss = max(out.ss, 0);
        }
        return out;
    }
};

struct FT{
    vector<int> bit, h;
    int n;
    FT(int ns){
        n = ns;
        bit.assign(n + 1, 1e9);
    }
    void clear(){
        for (int i: h){
            bit[i] = 1e9;
        }
        h.clear();
    }
    void upd(int v, int x){
        while (v <= n){
            h.pb(v);
            bit[v] = min(bit[v], x);
            v |= (v + 1);
        }
    }
    int get(int v){
        int out = 1e9;
        while (v > 0){
            out = min(out, bit[v]);
            v = (v & (v + 1)) - 1;
        }
        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);
    FT F(n);
    
    vector<pii> all, c;
    vector<arr3> f;
    
    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);
        
        all.clear();
        all.pb({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});
        }
        all.pb({d[x].back(), n});
        
        for (auto &[l, r]: all){
            pii f = T.get(l, r);
            l = f.ff; r = f.ss;
        }
        
        f.clear();
        for (int i = 0; i < all.size(); i++){
            f.pb({i + all[i].ff, i - all[i].ss, -(i + 1)});
            f.pb({i + all[i].ss, i - all[i].ff, i + 1});
        }
        
        auto cmp = [&](arr3 x, arr3 y){
            if (x[0] != y[0]) return x[0] < y[0];
            return x[2] < y[2];
        };
        
        sort(f.begin(), f.end(), cmp);
        c.clear();
        for (int i = 0; i < f.size(); i++){
            c.pb({f[i][1], i});
        }
        
        sort(c.begin(), c.end());
        int i = 0, cc = 0;
        while (i < c.size()){
            int j = i;
            while (j < c.size() && c[i].ff == c[j].ff){
                j++;
            }
            cc++;
            while (i < j){
                f[c[i].ss][1] = cc;
                i++;
            }
        }

        F.clear();
        for (auto [x, y, ii]: f){
            if (ii < 0){
                ii = -ii - 1;
                F.upd(y, ii);
                continue;
            }
            ii--;
            int t = F.get(y);
            out = max(out, ii - t);
        }

        for (int j: d[x]) T.add(j, n, -1);
    }
    return out;
}

• 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: 18 / 18