fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define mset(x,val) memset(x,val,sizeof(x))
  6. #define allof(x) x.begin(), x.end()
  7. #define fi first
  8. #define se second
  9.  
  10. using ll = long long;
  11. using vi = vector<int>;
  12. using vii = vector<vector<int>>;
  13. using vl = vector<long long>;
  14. using vll = vector<vector<long long>>;
  15. using vb = vector<bool>;
  16. using vbb = vector<vector<bool>>;
  17. using mii = map<int,int>;
  18. using umii = unordered_map<int,int>;
  19. using pii = pair<int,int>;
  20. using pll = pair<long long,long long>;
  21. using pli = pair<long long, int>;
  22. using pil = pair<int, long long>;
  23. #define __builtin_popcount __builtin_popcountll
  24. #define BIT(x, i) (((x) >> (i)) & 1)
  25. #define MASK(x) ((1ll << (x)))
  26. #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; 
  27.  
  28. const int maxn = 1e5 + 5;
  29.  
  30. int n,q;
  31.  
  32.  
  33. const ll MOD1 = 1e9+7;
  34. const ll MOD2 = 1e9+9;
  35. const ll BASE = 100001; 
  36.  
  37.  
  38. struct Hash
  39. {
  40.     ll h1, h2;
  41.  
  42.     bool operator == (const Hash &other) const
  43.     {
  44.         return (h1 == other.h1 && h2 == other.h2);
  45.     }
  46. };
  47.  
  48. vl pw1, pw2;
  49. vl inv_pw1, inv_pw2;
  50.  
  51. ll inv(ll x, ll mod)
  52. {
  53.     ll res=1, p=mod-2;
  54.     while (p)
  55.     {
  56.         if (p &1) res = res*x%mod;
  57.         x = x * x % mod;
  58.         p >>=1;
  59.     }
  60.     return res;
  61. }
  62.  
  63.  
  64. void precompute(int n)
  65. {
  66.     pw1.resize(n+5);
  67.     pw2.resize(n+5);
  68.     inv_pw1.resize(n+5);
  69.     inv_pw2.resize(n+5);
  70.     pw1[0] = pw2[0] = 1;
  71.  
  72.  
  73.     for (int i=1; i<=n; ++i) 
  74.     {
  75.         pw1[i] = pw1[i-1] * BASE % MOD1;
  76.         pw2[i] = pw2[i-1] * BASE % MOD2;
  77.     }
  78.  
  79.     inv_pw1[n] = inv(pw1[n], MOD1);
  80.     inv_pw2[n] = inv(pw2[n], MOD2);
  81.  
  82.  
  83.     for (int i=n-1; i>=0; --i)
  84.     {
  85.         inv_pw1[i] = inv_pw1[i+1] * BASE % MOD1;
  86.         inv_pw2[i] = inv_pw2[i+1] * BASE % MOD2;
  87.     }
  88.  
  89.  
  90.  
  91. }
  92.  
  93. vector <Hash> build_hash(string s, int n)
  94. {
  95.     vector <Hash> pref (n+5);
  96.     pref[0] = {0, 0};
  97.     for (int i=1; i<=n; ++i)
  98.     {
  99.         pref[i].h1 = (pref[i-1].h1 + 1LL * s[i-1] *pw1[i]) % MOD1;
  100.         pref[i].h2 = (pref[i-1].h2 + 1LL * s[i-1] * pw2[i]) % MOD2;
  101.     }
  102.     return pref;
  103. }   
  104.  
  105. Hash get_hash(int l, int r, vector<Hash> &pref)
  106. {
  107.     Hash res;
  108.     res.h1 = (pref[r].h1 - pref[l-1].h1 ) % MOD1;
  109.     res.h2 = (pref[r].h2 - pref[l-1].h2 ) % MOD2;
  110.  
  111.     if (res.h1 < 0) res.h1+=MOD1;
  112.     if (res.h2 < 0) res.h2+=MOD2;
  113.  
  114.     res.h1 = 1LL * res.h1 * inv_pw1[l] % MOD1;
  115.     res.h2 = 1LL * res.h2 * inv_pw2[l] % MOD2;
  116.  
  117.     return res;
  118. }
  119.  
  120. struct Eertree
  121. {
  122.     struct Node
  123.     {
  124.         int len;
  125.         int link;
  126.         int next[26];
  127.         ll cnt;
  128.         ll s_cnt;
  129.         int r;
  130.  
  131.         Node (int _n)
  132.         {
  133.             len = _n;
  134.             link = 0;
  135.             cnt = 0;
  136.             s_cnt = 0;
  137.             mset(next, 0);
  138.         }
  139.     };
  140.  
  141.     int n;
  142.     vector <Node> tree;
  143.     string s;
  144.     int last;
  145.  
  146.     Eertree(int _n)
  147.     {
  148.         n = _n;
  149.         tree.reserve(n+3);
  150.         tree.push_back(Node(-1));
  151.         tree.push_back(Node(0));
  152.  
  153.         tree[0].link = 0;
  154.         tree[1].link = 0;
  155.  
  156.         last = 1;
  157.         s="";
  158.     }
  159.  
  160.     int get_link(int v, int pos)
  161.     {
  162.         while (1)
  163.         {
  164.             int curlen = tree[v].len;
  165.             if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
  166.             v = tree[v].link;
  167.         }
  168.         return v;    
  169.     }
  170.  
  171.     void add_char(char c)
  172.     {
  173.         int pos = s.size();
  174.         s+=c;
  175.         int cur = get_link(last, pos);
  176.  
  177.         int cidx = c-'a';
  178.  
  179.         if (tree[cur].next[cidx])
  180.         {
  181.             last = tree[cur].next[cidx];
  182.             tree[last].cnt++;
  183.             tree[last].s_cnt++;
  184.             return;
  185.         }
  186.  
  187.         int new_node = tree.size();
  188.         tree.push_back(Node(tree[cur].len + 2));
  189.         tree[new_node].r = pos;
  190.  
  191.  
  192.         tree[cur].next[cidx] = new_node;
  193.  
  194.         if (tree[new_node].len == 1) 
  195.         {
  196.             tree[new_node].link = 1;
  197.  
  198.         }
  199.         else
  200.         {
  201.             int num = get_link(tree[cur].link, pos);
  202.             tree[new_node].link = tree[num].next[cidx];
  203.         }
  204.  
  205.         tree[new_node].cnt = 1;
  206.         tree[new_node].s_cnt = 1;
  207.         last = new_node;
  208.     }
  209.  
  210.     void build(string &str)
  211.     {
  212.         for (char &c : str) add_char(c);
  213.     }
  214.  
  215.     void propagate()
  216.     {
  217.         for (int i=tree.size()-1; i>=2; --i)
  218.         {
  219.             tree[tree[i].link].s_cnt += tree[i].s_cnt;
  220.         }
  221.     }
  222.  
  223.     int distinct_palin_cnt()
  224.     {
  225.         return tree.size() - 2; 
  226.     }
  227.  
  228.     ll palin_cnt()
  229.     {
  230.         ll res=0;
  231.  
  232.         for (int i=2; i<tree.size(); ++i) res+=tree[i].s_cnt;
  233.  
  234.         return res;
  235.     }
  236.  
  237.  
  238. };
  239.  
  240. string s;
  241.  
  242.  
  243. int get_lcp(int l1, int r1, int l2, int r2, vector<Hash> &pref)
  244. {
  245.     int low = 1 , high = min(r1 - l1 +1, r2 - l2 + 1), ans = 0;
  246.  
  247.     while(low <=high)
  248.     {
  249.         int mid = (low + high) >> 1;
  250.         if (get_hash(l1, l1 + mid-1, pref) == get_hash(l2, l2+mid-1, pref))
  251.         {
  252.             ans = mid;
  253.             low = mid+1;
  254.         }
  255.         else high = mid-1;
  256.     }
  257.     return ans;
  258. }
  259.  
  260.  
  261. void Input()
  262. {
  263.     cin >> n >> q;
  264.     cin>>s;
  265.     Eertree et = Eertree (n);
  266.     et.build(s);
  267.  
  268.     vector <pair<pii, int>> palins;
  269.     et.propagate();
  270.  
  271.     for (int i=2; i<et.tree.size(); ++i)
  272.     {
  273.         palins.push_back({{et.tree[i].r - et.tree[i].len + 2, et.tree[i].r + 1}, et.tree[i].s_cnt});
  274.     }
  275.  
  276.     precompute(n);
  277.     auto pref = build_hash(s, n);
  278.  
  279.     sort(allof(palins), [&](auto A, auto B)
  280.     {
  281.         int l1 = A.fi.fi, r1 = A.fi.se;
  282.         int l2 = B.fi.fi, r2 = B.fi.se;
  283.  
  284.         int lcp = get_lcp(l1, r1, l2, r2, pref);
  285.  
  286.         int len1= r1 - l1 + 1;
  287.         int len2= r2 - l2 + 1;
  288.  
  289.         if (lcp == min(len1, len2))
  290.         {
  291.             if (len1 != len2) return len1 < len2;
  292.             return l1 < l2;
  293.         }
  294.  
  295.         return s[l1 + lcp - 1] < s[l2 + lcp - 1]; 
  296.     });
  297.  
  298.     int m = palins.size();
  299.     vl pos(m+1, 0);
  300.     for (int i=1; i<=m; ++i)
  301.     {
  302.         pos[i] = pos[i-1] + palins[i-1].se;
  303.     }
  304.  
  305.     // for (int i=0; i<m; ++i)
  306.     // {
  307.     //     cout<<palins[i].fi.fi<< " "<<palins[i].fi.se<<" "<<palins[i].se<<'\n';
  308.     // }
  309.  
  310.     // debug(pos, 1, m);
  311.  
  312.     while (q--)
  313.     {
  314.         ll k;
  315.         cin>>k;
  316.  
  317.         if (k > pos[m]) 
  318.         {
  319.             cout<<-1<<'\n';
  320.             continue;
  321.         }
  322.         int p = lower_bound(pos.begin()+1, pos.end(), k) - pos.begin();
  323.  
  324.  
  325.         cout<<get_hash(palins[p-1].fi.fi, palins[p-1].fi.se, pref).h1  <<'\n';
  326.  
  327.     }
  328.  
  329.  
  330.  
  331. }
  332.  
  333. int main()
  334. {
  335.     ios::sync_with_stdio(0);
  336.     cin.tie(0);
  337.     cout.tie(0);
  338.  
  339.     Input();
  340.     return 0;
  341. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 7
abcba
1
2
3
4
6
7
8
stdout
copy 
97
97
696207567
98
29493435
99
-1
https://ideone.com/8m4WSx
Problem: https://o...content-available-to-author-only...i.info/problem/icpc22_mn_d
Verdict: Accepted
language:
C++14 (gcc 8.3)
created:
5 days 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!