fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #ifndef ONLINE_JUDGE
  7. #include "debug.cpp"
  8. #else
  9. #define dbg(...)
  10. #endif
  11. #define endl "\n"
  12. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
  13. #define ll long long
  14. #define pb(n) push_back(n)
  15. #define F first
  16. #define S second
  17. #define mp(x, y) make_pair(x, y)
  18. #define yes cout << "YES" << endl;
  19. #define no cout << "NO" << endl;
  20. #define nop cout << -1 << endl;
  21. #define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
  22. const ll sup = 1e18;
  23. const ll inf = -1e18;
  24. const ll mod = 1e9 + 7;
  25. const int N_Max = 2e5 + 7;
  26. const int Nax = 15;
  27. const int LOG = 18;
  28. const int BITS = 30;
  29. const int ALPHA = 26;
  30. ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
  31. ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
  32. ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
  33.  
  34. const ll B = 9973;
  35. ll prefix[N_Max], suffix[N_Max];
  36. int N;
  37.  
  38. ll binpow(ll a, ll b){
  39.     ll res = 1;
  40.     while (b > 0) {
  41.         if (b & 1)
  42.             res = res * a % mod;
  43.         a = a * a % mod;
  44.         b >>= 1;
  45.     }
  46.     return res;
  47. }
  48.  
  49. ll bs2(int i, int p, int re){
  50.     int lo = i - re - 1, ro = p + re + 1;
  51.     if (lo < 0 || ro >= N) return 0;
  52.     int l = 0, r = min(N - 1 - ro, lo), ret = 0;
  53.     dbg(l);
  54.     dbg(r);
  55.     while (l <= r){
  56.         int mid = l + (r - l) / 2;
  57.         int j = ro + mid, k = lo - mid;
  58.         ll hash1 = (prefix[j] - prefix[ro] + mod) % mod * inv(binpow(B, ro) % mod) % mod;
  59.         ll hash2 = (suffix[k] - suffix[lo] + mod) % mod * inv(binpow(B, N - 1 - lo) % mod) % mod;
  60.         if (hash1 == hash2){
  61.             ret = j;
  62.             l = mid + 1;
  63.         }
  64.         else r = mid - 1;
  65.     }
  66.     dbg(ret);
  67.     return ret + 1;
  68. }
  69.  
  70. ll bs1(int i, int p){
  71.     int l = 0, r = min(i, N - 1 - p), ret = 0;
  72.     while (l <= r){
  73.         int mid = l + (r - l) / 2;
  74.         int d = mid - i;
  75.         int j = i - mid, k = p + mid;
  76.         ll hash1 = (prefix[k] - prefix[p] + mod) % mod * inv(binpow(B, p + 1)) % mod;
  77.         ll hash2 = (suffix[j] - suffix[i] + mod) % mod * inv(binpow(B, N - 1 - i)) % mod;
  78.         if (hash1 == hash2){
  79.             ret = mid;
  80.             l = mid + 1;
  81.         }
  82.         else r = mid - 1;
  83.     }
  84.     int co = bs2(i, p, ret);
  85.     dbg(co);
  86.     ret += co;
  87.     return ret;
  88. }
  89.  
  90. void solve(){
  91.     string s;
  92.     cin >> N >> s;
  93.     for (int i = 0; i < N; i++){
  94.         ll c = (s[i] - 'a') + 1;
  95.         ll pre = (i == 0 ? 0 : prefix[i - 1]);
  96.         prefix[i] = (pre + c * binpow(B, i) % mod) % mod;
  97.     }
  98.     for (int i = N - 1; i >= 0; i--){
  99.         ll c = (s[i] - 'a') + 1;
  100.         ll nxt = (i == N - 1 ? 0 : suffix[i + 1]);
  101.         suffix[i] = (nxt + c * binpow(B, N - 1 - i) % mod) % mod;
  102.     }
  103.     ll ans = 0;
  104.     for (int i = 0; i < N; i++){
  105.         ll ret = bs1(i, i);
  106.         dbg(i);
  107.         dbg(ret);
  108.         cout << endl;
  109.         ans += ret + 1;
  110.         if (i + 1 < N && s[i] == s[i + 1])
  111.             ans += bs1(i, i + 1) + 1;
  112.         else if (i + 1 < N && s[i] != s[i + 1])
  113.             ans += bs2(i + 1, i - 1, 0) + 1;
  114.     }
  115.     cout << ans << endl;
  116. }
  117.  
  118. int main(){
  119.     FAST
  120.     #ifndef ONLINE_JUDGE
  121.     freopen("input.txt","r",stdin);
  122.     freopen("output.txt","w",stdout);
  123.     #endif
  124.     int tc = 1;
  125.     // cin >> tc;
  126.     while (tc--) solve();
  127.     return 0;
  128. }
Success #stdin #stdout 0.01s 5376KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/fQE0sP
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

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!