Submission #74672866

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define se second
#define fi first
#define pb push_back
#define pf push_front
#define ld long double
#define INF 1e18
#define lcm(x, y) x / __gcd(x, y) * y
#define Pair pair<ll, ll>
#define pii pair<int, int>
#define Pq priority_queue<ll>
#define Pqr priority_queue<ll, vector<ll>, greater<ll >>
#define clockst clock_t tStart = clock()
#define clockfin printf("Time taken: %.2fs\n",(double)(clock() - tStart)/CLOCKS_PER_SEC)
#define all(x) x.begin(), x.end()
#define sz(x)((ll)(x).size())
#define eb emplace_back
#define mp make_pair
#define mems(a, x) memset((a),(x), sizeof(a))
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2,fma")
typedef unsigned long long ull;
void init() { freopen("cf.INP", "r", stdin); freopen("cf.OUT", "w", stdout); }
ll xc[5] = { -1, 1, 0, 0 }, yc[5] = { 0, 0, 1, -1 };
ll xc8[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };
ll yc8[8] = { 0, 0, 1, -1, -1, 1, 1, -1 };
const long double pi = acosl(-1.0L);
template<class T1, class T2> bool cmax(T1 &x, const T2 &y) { if(x < y) { x = y; return 1; } return 0; }

inline ll read()
{
    ll x = 0;
    char ch = getchar();;
    bool str = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') str = 0; ch = getchar();;
    }
    while(ch >= '0' && ch <= '9')
    {
        x =((x << 3) +(x << 1)) + ch - '0';
        ch = getchar();;
    }
    return str ? x : x;
}

struct seg {
    ll len, link;
    ll nxt[10];
};

vector<seg> st;
ll sz;

void precomp()
{
    st.clear();
    st.reserve(1000005);
    seg s0;
    s0.len = 0; s0.link = -1;
    fill(s0.nxt, s0.nxt + 10, -1);
    st.push_back(s0);
    sz = 1;
}

ll saex(ll last, ll c)
{
    if (st[last].nxt[c] != -1)
    {
        ll q = st[last].nxt[c];
        if (st[last].len + 1 == st[q].len)
        {
            return q;
        }
        ll clone = sz++;
        st.push_back(st[q]);
        st[clone].len = st[last].len + 1;
        ll p = last;
        while (p != -1 && st[p].nxt[c] == q)
        {
            st[p].nxt[c] = clone;
            p = st[p].link;
        }
        st[q].link = clone;
        return clone;
    }
    ll cur = sz++;
    seg ns;
    ns.len = st[last].len + 1;
    ns.link = -1;
    fill(ns.nxt, ns.nxt + 10, -1);
    st.push_back(ns);
    ll p = last;
    while (p != -1 && st[p].nxt[c] == -1)
    {
        st[p].nxt[c] = cur;
        p = st[p].link;
    }
    if (p == -1)
    {
        st[cur].link = 0;
    }
    else
    {
        ll q = st[p].nxt[c];
        if (st[p].len + 1 == st[q].len)
        {
            st[cur].link = q;
        }
        else
        {
            ll clone = sz++;
            st.pb(st[q]);
            st[clone].len = st[p].len + 1;
            while (p != -1 && st[p].nxt[c] == q)
            {
                st[p].nxt[c] = clone;
                p = st[p].link;
            }
            st[q].link = clone;
            st[cur].link = clone;
        }
    }
    return cur;
}

void solve()
{
    fast;
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for (ll i = 1; i <= n; i++) cin >> a[i];
    vector<bool> ok(n + 2, 0);
    for (ll i = 1; i <= n; i++)
    {
        ll d = a[i];
        if (i + d - 1 > n) continue;
        bool good = 1;
        for (ll t = i; t < i + d; t++)
        {
            if (a[t] != d) { good = 0; break; }
        }
        ok[i] = good;
    }
    vector<ll> nxt(n + 2, -1);
    for (ll i = 1; i <= n; i++)
    {
        if (!ok[i]) continue;
        ll d = a[i];
        ll j = i + d;
        if (j <= n && a[j] != d && ok[j]) nxt[i] = j;
    }
    vector<vector<ll>> c(n + 2);
    vector<bool> hasp(n + 2, 0);
    for (ll i = 1; i <= n; i++)
    {
        if (!ok[i]) continue;
        if (nxt[i] != -1)
        {
            c[nxt[i]].pb(i);
            hasp[i] = 1;
        }
    }
    vector<ll> root;
    for (ll i = 1; i <= n; i++)
    {
        if (ok[i] && !hasp[i]) root.pb(i);
    }
    precomp();
    vector<ll> sid(n + 2, -1);
    stack<Pair> stk;
    for (ll r : root) stk.push({r, 0});
    while (!stk.empty())
    {
        auto k = stk.top(); stk.pop();
        auto u = k.fi;
        auto par_state = k.se;
        ll cur = saex(par_state, a[u] - 1);
        sid[u] = cur;
        for (ll v : c[u]) stk.push({v, cur});
    }
    vector<bool> term(sz, 0);
    for (ll i = 1; i <= n; i++)
    {
        if (ok[i] && sid[i] != -1) term[sid[i]] = 1;
    }
    vector<ll> order(sz);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [](ll a, ll b) {
        return st[a].len > st[b].len;
    });
    for (ll v : order)
    {
        if (term[v] && st[v].link != -1) term[st[v].link] = 1;
    }
    ll ans = 0;
    for (ll i = 1; i < sz; i++)
    {
        if (term[i]) ans += st[i].len - st[st[i].link].len;
    }
    cout << ans << '\n';
}

bool multest = 0;

int main()
{
    fast;
    ll t = 1;
    if(multest) cin >> t;
    while(t--) solve();
    return 0;
}

Submission Info

Judge Result