Submission #74682098

---

Source Code Expand

#include<bits/extc++.h>

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx,avx2")

#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#include<map>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define coutc "\033[48;5;196m\033[38;5;15m"
#define endc "\033[0m"
#define M(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) \
  M(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rep4(_, x, n, s) \
  for (int _ = x; (s < 0) ? _ > n : _ < n; _ += s)
#define rep3(_, x, n) rep4(_, x, n, (x < n ? 1 : -1))
#define rep2(_, n) rep3(_, 0, n)
#define rep1(n) rep2(i, n)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)

#define mp make_pair
// #define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define endl "\n"

// #define cin fin
// #define cout fout

// ifstream fin("word.in");
// ofstream fout("word.out");

const int inf = INT_MAX;
const int MOD = 1000000007;
double PI = 4*atan(1);

#ifdef DEBUG
string to_string(char c) { return string({c}); }
// 7
template<class... Ts>
ostream& operator<<(ostream& o, tuple<Ts...> t) {
  string s = "(";
  apply([&](auto&&... r) {
    ((s += to_string(r) + ", "), ...); }, t);
  return o << s.substr(0, len(s) - 2) + ")";
}
// 3
ostream& operator<<(ostream &o, pair<auto, auto> p) {
  return o << "(" << p.fi << ", " << p.se << ")";
}
// 7
template<class C, class T = typename C::value_type,
typename std::enable_if<!std::is_same<C, std::string>
::value>::type* = nullptr>
ostream& operator<<(ostream &o, C c) {
  for (auto e : c) o << setw(7) << right << e;
  return o << endc << endl << coutc;
}
// 7
void debug(const auto &e, const auto &... r) {
  cout << coutc << e;
  ((cout << " " << r), ..., (cout << endc << endl));
}
#else
#define debug(...)
#endif

map<string,int> mon;
map<int,string> inp;

void _main(int tc) {
    int n;
    cin >> n;
    vi a(n);
    int i = 0;
    while (i < n) cin >> a[i], i++;

    vi c, l;
    i = 0;
    while (i < n) {
        if (c.empty() || c.back() != a[i]) c.push_back(a[i]), l.push_back(1);
        else l.back()++;
        i++;
    }

    int r = (int)c.size();
    vi cap(r), good(r), bad;
    i = 0;
    while (i < r) {
        cap[i] = (l[i] >= c[i]);
        good[i] = (l[i] == c[i]);
        if (!good[i]) bad.push_back(i);
        i++;
    }

    vector<pi> seg;
    if (bad.empty()) seg.push_back({0, r - 1});
    else {
        seg.push_back({0, bad[0]});
        i = 0;
        while (i + 1 < (int)bad.size()) {
            seg.push_back({bad[i], bad[i + 1]});
            i++;
        }
        seg.push_back({bad.back(), r - 1});
    }

    vi s, w;
    i = 0;
    while (i < (int)seg.size()) {
        int L = seg[i].f, R = seg[i].s;
        int mx = cap[R] ? R : R - 1;
        int p = L;
        while (p <= R) {
            s.push_back(c[p]);
            int cur = 0;
            if (cap[p] && p <= mx) cur = mx - p + 1;
            w.push_back(cur);
            p++;
        }
        s.push_back(0);
        w.push_back(0);
        i++;
    }

    reverse(s.begin(), s.end());
    reverse(w.begin(), w.end());

    int m = (int)s.size();
    int mxs = 2 * m + 5;
    vi to(mxs * 10, -1), link(mxs), len(mxs), best(mxs), cnt(m + 1), ord(mxs);
    int sz = 1, last = 0;
    link[0] = -1;
    len[0] = 0;

    auto cp = [&](int x, int y) {
        int j = 0;
        while (j < 10) {
            to[x * 10 + j] = to[y * 10 + j];
            j++;
        }
    };

    auto nw = [&](int L) {
        int id = sz++;
        len[id] = L;
        link[id] = -1;
        best[id] = 0;
        int j = 0;
        while (j < 10) {
            to[id * 10 + j] = -1;
            j++;
        }
        return id;
    };

    auto ext = [&](int ch) {
        int cur = nw(len[last] + 1);
        int p = last;
        while (p != -1 && to[p * 10 + ch] == -1) {
            to[p * 10 + ch] = cur;
            p = link[p];
        }
        if (p == -1) link[cur] = 0;
        else {
            int q = to[p * 10 + ch];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int cl = nw(len[p] + 1);
                cp(cl, q);
                link[cl] = link[q];
                while (p != -1 && to[p * 10 + ch] == q) {
                    to[p * 10 + ch] = cl;
                    p = link[p];
                }
                link[q] = link[cur] = cl;
            }
        }
        last = cur;
        return cur;
    };

    vi pos(m);
    i = 0;
    while (i < m) {
        pos[i] = ext(s[i]);
        if (w[i] > best[pos[i]]) best[pos[i]] = w[i];
        i++;
    }

    i = 0;
    while (i < sz) cnt[len[i]]++, i++;
    i = 1;
    while (i <= m) cnt[i] += cnt[i - 1], i++;
    i = sz - 1;
    while (i >= 0) ord[--cnt[len[i]]] = i, i--;
    i = sz - 1;
    while (i > 0) {
        int v = ord[i];
        int p = link[v];
        if (p >= 0 && best[v] > best[p]) best[p] = best[v];
        i--;
    }

    ll ans = 0;
    i = 1;
    while (i < sz) {
        int up = min(len[i], best[i]);
        int lo = len[link[i]];
        if (up > lo) ans += up - lo;
        i++;
    }
    cout << ans << endl;
}
// 5
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0), exit(0);
  int tc; cin >> tc; rep(i, tc) _main(i + 1);
}

Submission Info

Compile Error

./Main.cpp: In function 'void _main(int)':
./Main.cpp:92:16: warning: unused parameter 'tc' [-Wunused-parameter]
   92 | void _main(int tc) {
      |            ~~~~^~

Judge Result