fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define base 267LL
  5. #define mod 1000'000'000'000'000'003LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  8. ll gen(ll l, ll r){
  9.     return uniform_int_distribution<ll>(1, LLONG_MAX - 1)(rng);
  10. }
  11. ll mul(ll a, ll b){
  12.     __int128_t v = a;
  13.     return v * b % mod;
  14. }
  15. void solve() {
  16.     ll n;
  17.     cin >> n;
  18.     vector <ll> l1(n);
  19.     vector <vector <ll>> adj(n+1);
  20.     vector <ll> pow(n+1);
  21.     vector <ll> cnt(n+1, 0);
  22.     pow[0] = 1;
  23.     for (int i = 1; i <= n; i++){
  24.         pow[i] = mul(pow[i-1], base);
  25.     }
  26.     ll answ = 0;
  27.     ll lo = -1; ll v = 0;
  28.     map <ll,vector <ll>> f;
  29.     FOR(i,0,n) cin >> l1[i];
  30.     f[0].push_back(-1);
  31.     FOR(i,0,n){
  32.         adj[l1[i]].push_back(i);
  33.         v -= mul(cnt[l1[i]],pow[l1[i]]);
  34.         cnt[l1[i]] = (cnt[l1[i]] + 1) % 3;
  35.         v = ((v + mul(cnt[l1[i]], pow[l1[i]])) % mod + mod) % mod;
  36.         if (adj[l1[i]].size() > 3){
  37.             ll sz = adj[l1[i]].size();
  38.             lo = max(lo, adj[l1[i]][sz - 4]);
  39.         }
  40.         auto cur = &f[v];
  41.         auto it = lower_bound(cur->begin(), cur->end(), lo);
  42.         ll pos = it - cur->begin();
  43.         answ += cur->size() - pos;
  44.         f[v].push_back(i);
  45.     }
  46.     cout << answ << "\n";
  47. }
  48.  
  49. int main() {
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.  
  53.     ll t = 1;
  54.     while (t--) {
  55.         solve();
  56.     }
  57.  
  58.     return 0;
  59. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9ROJmR
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!