API tools faq
paste
mr_dot_convict

873F-Forbidden-Indices-codeforces-mr.convict

mr_dot_convict
May 5th, 2020
122
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.05 KB | None | 0 0
raw download clone embed print report
  1. // Hack it and have it ;) //
  2. /*author* Priyanshu Shrivastav (from IIT Palakkad) *
  3.  * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
  4.  * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
  5.  * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
  6.  * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
  7. When I wrote this, only God and I understood what I was doing
  8.  ** * * * * * * * Now, only God knows!* * * * * * */
  9. #include      <bits/stdc++.h> /*{{{*/
  10. #include      <ext/pb_ds/assoc_container.hpp>
  11. #include      <ext/pb_ds/tree_policy.hpp>
  12. using namespace std;
  13. using namespace __gnu_pbds;
  14.  
  15. #ifndef CONVICTION
  16. #pragma GCC       optimize ("Ofast")
  17. #pragma GCC       optimize ("unroll-loops")
  18. #pragma GCC       target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  19. #endif
  20.  
  21. #define IOS       ios_base::sync_with_stdio(false); cin.tie (nullptr)
  22. #define PREC      cout.precision (10); cout << fixed
  23. #define X         first
  24. #define Y         second
  25. #define sz(x)     (int)x.size()
  26. #define fr(i,x,y) for (int i = (int)x; i <= (int)y; ++i)
  27. #define rv(i,x,y) for (int i = (int)x; i >= (int)y; --i)
  28. #define bcnt(x)   __builtin_popcount(x)
  29. #define bcntll(x) __builtin_popcountll(x)
  30. #define bg(x)     " [ " << #x << " : " << (x) << " ] "
  31. #define un(x)     sort(x.begin(), x.end()), \
  32.   x.erase(unique(x.begin(), x.end()), x.end())
  33. using   ll  =     long long;
  34. using   ull =     unsigned long long;
  35. using   ff  =     long double;
  36. using   pii =     pair<int,int>;
  37. using   pil =     pair<int,ll>;
  38. using   pll =     pair<ll,ll>;
  39. using   vi  =     vector <int>;
  40. using   vl  =     vector<ll>;
  41. using   vvi =     vector <vi>;
  42. using   vvl =     vector <vl>;
  43. using   vp  =     vector <pii>;
  44. using   vvp =     vector <vp>;
  45. typedef tree
  46. < int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  47. ordered_set;
  48.  
  49. struct chash {
  50.   int operator () (pii x) const { return x.X*31 + x.Y; }
  51. };
  52. gp_hash_table <pii, int, chash> gmp;
  53.  
  54. #if __cplusplus > 201103L
  55. seed_seq seq{
  56.   (uint64_t) chrono::duration_cast<chrono::nanoseconds>
  57.     (chrono::high_resolution_clock::now().time_since_epoch()).count(),
  58.     (uint64_t) __builtin_ia32_rdtsc(),
  59.     (uint64_t) (uintptr_t) make_unique<char>().get()
  60. };
  61. mt19937 rng(seq); //uniform_int_distribution<int> (l, h)(rng); //[low, high]
  62. #else
  63. auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  64. mt19937 rng(seed);
  65. #endif
  66.  
  67. #ifdef CONVICTION
  68. void __print(int x) {cerr << x;}
  69. void __print(long x) {cerr << x;}
  70. void __print(long long x) {cerr << x;}
  71. void __print(unsigned x) {cerr << x;}
  72. void __print(unsigned long x) {cerr << x;}
  73. void __print(unsigned long long x) {cerr << x;}
  74. void __print(float x) {cerr << x;}
  75. void __print(double x) {cerr << x;}
  76. void __print(long double x) {cerr << x;}
  77. void __print(char x) {cerr << '\'' << x << '\'';}
  78. void __print(const char *x) {cerr << '\"' << x << '\"';}
  79. void __print(const string &x) {cerr << '\"' << x << '\"';}
  80. void __print(bool x) {cerr << (x ? "true" : "false");}
  81.  
  82. template<typename T, typename V>
  83. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  84. template<typename T>
  85. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  86. void _print() {cerr << "]\n";}
  87. template <typename T, typename... V>
  88. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  89. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  90. #else
  91. #define debug(x...)
  92. #endif
  93. //         __                                           __
  94. //        (**)                                         (**)
  95. //        IIII                                         IIII
  96. //        ####                                         ####
  97. //        HHHH     Madness comes, and madness goes     HHHH
  98. //        HHHH    An insane place, with insane moves   HHHH
  99. //        ####   Battles without, for battles within   ####
  100. //     ___IIII___        Where evil lives,          ___IIII___
  101. //  .-`_._"**"_._`-.      and evil rules         .-`_._"**"_._`-.
  102. // |/``  .`\/`.  ``\|    Breaking them up,      |/``  .`\/`.  ``\|
  103. // `     }    {     '  just breaking them in    `     }    {     '
  104. //       ) () (  Quickest way out, quickest way wins  ) () (
  105. //       ( :: )      Never disclose, never betray     ( :: )
  106. //       | :: |   Cease to speak or cease to breath   | :: |
  107. //       | )( |        And when you kill a man,       | )( |
  108. //       | || |          you're a murderer            | || |
  109. //       | || |             Kill many                 | || |
  110. //       | || |        and you're a conqueror         | || |
  111. //       | || |        Kill them all ... Ooh..        | || |
  112. //       | || |           Oh you're a God!            | || |
  113. //       ( () )                       -Megadeth       ( () )
  114. //        \  /                                         \  /
  115. //         \/                                           \/
  116. /*}}}*/
  117. /*****************************************************************************/
  118. //Don’t practice until you get it right. Practice until you can’t get it wrong
  119.  
  120. struct suffix_array {
  121.   const int Log = 20;
  122.  
  123.   string s;
  124.   vector <vector <int>> p, c;
  125.   vector <int> lp, sa;
  126.   int n;
  127.  
  128.   void cyclic_sort () { // O(|s| * (log|s|)^2)
  129.     iota(p[0].begin(), p[0].end(), 0);
  130.     sort (p[0].begin(), p[0].end(), [&] (const int &x, const int &y) -> bool {
  131.         return s[x] < s[y];
  132.         });
  133.  
  134.     int ck = 0;
  135.     c[0][p[0][0]] = ck;
  136.     for (int i = 1; i < n; ++i)
  137.       c[0][p[0][i]] = ck += (s[p[0][i]] != s[p[0][i - 1]]);
  138.  
  139.     for (int k = 1; k <= Log; ++k) {
  140.       int pw = 1 << (k - 1);
  141.       iota(p[k].begin(), p[k].end(), 0);
  142.  
  143.       sort (p[k].begin(), p[k].end(), [&] (const int &x, const int &y) -> bool {
  144.           return c[k - 1][x] < c[k - 1][y] ||
  145.           (c[k - 1][x] == c[k - 1][y] &&
  146.            c[k - 1][(x + pw) % n] < c[k - 1][(y + pw) % n]);
  147.           });
  148.  
  149.       c[k][p[k][0]] = ck = 0;
  150.       for (int i = 1; i < n; ++i)
  151.         c[k][p[k][i]] =
  152.           ck += (c[k - 1][p[k][i]] != c[k - 1][p[k][i - 1]]
  153.               || c[k - 1][(p[k][i] + pw) % n] != c[k - 1][(p[k][i - 1] + pw) % n]);
  154.     }
  155.   }
  156.  
  157.   int lcp(int i, int j) { // in cyclic string (NOTE, otherwise change starting value of k)
  158.     int res = 0;
  159.     for (int k = Log; k >= 0; --k) {
  160.       if (i + (1 << k) - 1 > n || j + (1 << k) - 1 > n) continue; // to remove the cyclic constraint
  161.       if (c[k][i] == c[k][j])
  162.         i += (1 << k), j += (1 << k), res += (1 << k);
  163.     }
  164.     return res;
  165.   }
  166.  
  167.   suffix_array (string s_) {
  168.     s = s_ + "$";
  169.     n = (int)s.size();
  170.     p.assign(Log + 1, vector <int> (n));
  171.     c.assign(Log + 1, vector <int> (n));
  172.     sa.assign(n + 1, 0);
  173.     lp.assign(n + 1, 0);
  174.  
  175.     cyclic_sort();
  176.     for (int i = 0; i < n; ++i) {
  177.       sa[i] = p[Log][i];
  178.       if (i != n - 1) lp[i] = lcp(p[Log][i], p[Log][i + 1]);
  179.     }
  180.   }
  181.  
  182.   int compare (int i, int j, int k, int len) { // O(1)
  183.     pair <int, int> s1 = make_pair(c[k][i], c[k][(i + len - (1 << k)) % n]);
  184.     pair <int, int> s2 = make_pair(c[k][j], c[k][(j + len - (1 << k)) % n]);
  185.     return s1 == s2 ? 0 : s1 < s2 ? -1 : 1;
  186.   }
  187.  
  188.   friend ostream& operator << (ostream &os, const suffix_array &S) {
  189.     for (int i = 0; i < S.n; ++i) {
  190.       os << S.s.substr(i, S.n - i) << '\n';
  191.     }
  192.     return os;
  193.   }
  194. };
  195.  
  196. #define T(x) (1 << (x))
  197. void solve() {
  198.   const int D = 20;
  199.   int n;
  200.   string s, idx;
  201.   cin >> n >> s >> idx;
  202.   reverse(s.begin(), s.end());
  203.   reverse(idx.begin(), idx.end());
  204.   suffix_array S(s);
  205.  
  206.   vector <int> use, lcp;
  207.   for (int i = 0; i < n; ++i) {
  208.     if (idx[i] == '0') use.push_back(i);
  209.   }
  210.   if (use.size() == 0) {
  211.     cout << 0 << '\n';
  212.     return;
  213.   }
  214.   sort(use.begin(), use.end(), [&] (int p, int q) -> bool {
  215.       return S.c[S.Log][p] < S.c[S.Log][q];
  216.       });
  217.  
  218.   int sz = (int)use.size();
  219.   lcp.assign(sz - 1, 0);
  220.   for (int i = 0; i < sz - 1; ++i) {
  221.     lcp[i] = S.lcp(use[i], use[i + 1]); } // debug(use, lcp);
  222.  
  223.   vector <vector <int>> dp(sz - 1, vector <int> (D + 1));
  224.   {
  225.     for (int i = 0; i < sz - 1; ++i)
  226.       dp[i][0] = lcp[i];
  227.     for (int k = 1; k <= D; ++k) {
  228.       for (int i = 0; i < sz - 1; ++i) {
  229.         if (i + T(k) - 1 < sz - 1)
  230.           dp[i][k] = min(dp[i][k - 1], dp[i + T(k - 1)][k - 1]);
  231.       }
  232.     }
  233.   }
  234.  
  235.   long long mx = 0;
  236.   {
  237.     for (int i = 0; i < sz - 1; ++i) {
  238.       if (dp[i][0] == 0) continue;
  239.       int L = i, R = i;
  240.       for (int k = D; k >= 0; --k) {
  241.         if (R + T(k) - 1 < sz - 1 && dp[R][k] >= dp[i][0])
  242.           R += T(k);
  243.       }
  244.       --R;
  245.       for (int k = D; k >= 0; --k) {
  246.         if (L - T(k) + 1 >= 0 && dp[L - T(k) + 1][k] >= dp[i][0])
  247.           L -= T(k);
  248.       }
  249.       ++L;
  250.       // debug(i, L, R, dp[i][0]);
  251.       mx = max(mx, 1ll * (R - L + 2) * dp[i][0]);
  252.     }
  253.     for (int i = 0; i < sz; ++i)
  254.       mx = max(mx, 1ll * n - use[i]);
  255.   }
  256.   cout << mx << '\n';
  257. }
  258.  
  259. signed main() {
  260.   IOS; PREC;
  261.   int tc = 1;
  262.   // cin >> tc;
  263.   for (int Tt = 1; Tt <= tc; ++Tt) {
  264.     // cout << "Case #" << Tt << ": ";
  265.     solve();
  266.   }
  267.   return EXIT_SUCCESS;
  268. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!