fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int BASE = 2;
  5. const int INVBASE1 = 500000004, INVBASE2 = 500000005;
  6. const int N = 1e6 + 5;
  7.  
  8. pair<int, int> MOD = make_pair(1e9 + 7, 1e9 + 9);
  9. pair<int, int> POWBASE[N], INVPOWBASE[N];
  10. pair<int, int> pre[N], suf[N];
  11. int S[N];
  12. int best_even[N], best_odd[N];
  13.  
  14. pair<int, int> add(pair<int, int> a, pair<int, int> b) {
  15.   pair<int, int> res = make_pair((a.first + b.first) % MOD.first, (a.second + b.second) % MOD.second);
  16.   if(res.first < 0)   res.first += MOD.first;
  17.   if(res.second < 0)  res.second += MOD.second;
  18.   return res;
  19. }
  20.  
  21. pair<int, int> mult(pair<int, int> a, pair<int, int> b) {
  22.   pair<int, int> res = make_pair((a.first * 1LL * b.first) % MOD.first, (a.second * 1LL * b.second) % MOD.second);
  23.   if(res.first < 0)   res.first += MOD.first;
  24.   if(res.second < 0)  res.second += MOD.second;
  25.   return res;
  26. }
  27.  
  28. pair<int, int> neg(pair<int, int> a) {
  29.   pair<int, int> res = make_pair(-a.first, -a.second);
  30.   if(a.first < 0)   res.first += MOD.first;
  31.   if(a.second < 0)  res.second += MOD.second;
  32.   return res;
  33. }
  34.  
  35. bool is_palin(int l, int r) {
  36.   if(l < 0 or l > r)  return 0;
  37.   int mid = (l + r)/2;
  38.   pair<int, int> lhash = mult(add(pre[mid], l - 1 >= 0 ? neg(pre[l - 1]) : make_pair(0, 0)), INVPOWBASE[l]);
  39.   if((r - l + 1) % 2 == 0)  mid++;
  40.   pair<int, int> rhash = add(suf[r], mult(POWBASE[r - mid + 1], mid - 1 >= 0 ? neg(suf[mid - 1]) : make_pair(0, 0)));
  41.   int b1 = (lhash == rhash);
  42.   /*
  43.   int b2 = 1;
  44.   for(int i = l; i <= r; i++)
  45.     if(S[i] != S[r + l - i])  b2 = 0;
  46.   if(b1 != b2) {
  47.     cerr<<l<<" "<<r<<" brute: "<<b2<<", sol: "<<b1<<endl;
  48.     for(int i = l; i <= r; i++) cerr<<S[i];
  49.     cerr<<endl;
  50.     cerr<<lhash.first<<" "<<rhash.first<<endl;
  51.     assert(false);
  52.   }
  53.   */
  54.   return b1;
  55. }
  56.  
  57. int main() {
  58.   cin.tie(NULL);
  59.   ios::sync_with_stdio(false);
  60.   cout.tie(NULL);
  61.   POWBASE[0] = {1, 1};
  62.   for(int i = 1; i < N; i++)  POWBASE[i] = mult(POWBASE[i - 1], {BASE, BASE});
  63.   INVPOWBASE[0] = {1, 1};
  64.   for(int i = 1; i < N; i++)  INVPOWBASE[i] = mult(INVPOWBASE[i - 1], {INVBASE1, INVBASE2});
  65.  
  66.   int n, type, ptr = -1, d;
  67.   cin>>n;
  68.   assert(n >= 1 and n <= 1000000);
  69.   for(int i = 0; i < n; i++) {
  70.     cin>>type;
  71.     if(type == 1) {
  72.       cin>>d;
  73.       assert(d >= 0 and d <= 1);
  74.       ptr++;
  75.       S[ptr] = d;
  76.       pre[ptr] = add(ptr - 1 >= 0 ? pre[ptr - 1] : make_pair(0, 0), mult({d, d}, POWBASE[ptr]));
  77.       suf[ptr] = add(ptr - 1 >= 0 ? mult(suf[ptr - 1], {BASE, BASE}) : make_pair(0, 0), {d, d});
  78.       int prev_odd = ptr - 1 >= 0 ? best_odd[ptr - 1] : -1;
  79.       best_odd[ptr] = is_palin(ptr - (prev_odd + 2) + 1, ptr) ? prev_odd + 2 : prev_odd;
  80.       int prev_even = ptr - 1 >= 0 ? best_even[ptr - 1] : 0;
  81.       best_even[ptr] = is_palin(ptr - (prev_even + 2) + 1, ptr) ? prev_even + 2 : prev_even;
  82.     } else if(type == 2) {
  83.       ptr--;
  84.     } else {
  85.       assert(false);
  86.     }
  87.     assert(ptr >= -1);
  88.     if(ptr == -1) cout<<0<<'\n';
  89.     else          cout<<max(best_odd[ptr], best_even[ptr])<<'\n';
  90.   }
  91. }
  92.  
Runtime error #stdin #stdout #stderr 0.04s 19092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:68: int main(): Assertion `n >= 1 and n <= 1000000' failed.
https://ideone.com/FbxVg2
language:
C++14 (gcc 8.3)
created:
4 years 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!