fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define sz(a) (int)(a).size()
  5. #define all(a) (a).begin(), (a).end()
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #include <bits/stdc++.h>
  10.  
  11. using namespace __gnu_pbds;
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef pair<int, int> pii;
  17.  
  18. typedef
  19. tree<
  20.   pii,
  21.   null_type,
  22.   less<pii>,
  23.   rb_tree_tag,
  24.   tree_order_statistics_node_update>
  25. ordered_set;
  26.  
  27. const int nmax = 1e6 + 100;
  28. const int inf = 1e9;
  29. const int rmax = 22;
  30.  
  31. int sparse[rmax][nmax];
  32. int deg[nmax];
  33.  
  34. int p[nmax], pos[nmax], lcp[nmax];
  35. int cnt[nmax];
  36. int c[nmax];
  37. int cn[nmax], pn[nmax];
  38.  
  39. void suffixArray(const string& s) {
  40.     int n = sz(s);
  41.     for (int i = 0; i < n; ++i) {
  42.         ++cnt[s[i]];
  43.     }
  44.     for (int i = 1; i < nmax; ++i) {
  45.         cnt[i] += cnt[i - 1];
  46.     }
  47.     for (int i = n - 1; i >= 0; --i) {
  48.         p[--cnt[s[i]]] = i;
  49.     }
  50.     c[p[0]] = 0;
  51.     for (int i = 1; i < n; ++i) {
  52.         c[p[i]] = c[p[i - 1]];
  53.         if (s[p[i]] != s[p[i - 1]]) {
  54.             ++c[p[i]];
  55.         }
  56.     }
  57.     int len = 1;
  58.     for (int j = 0; len < n; ++j, len <<= 1) {
  59.         for (int i = 0; i < n; ++i) {
  60.             pn[i] = p[i] - len;
  61.             if (pn[i] < 0) {
  62.                 pn[i] += n;
  63.             }
  64.         }
  65.         memset(cnt, 0, sizeof(cnt));
  66.         for (int i = 0; i < n; ++i) {
  67.             ++cnt[c[i]];
  68.         }
  69.         for (int i = 1; i < n; ++i) {
  70.             cnt[i] += cnt[i - 1];
  71.         }
  72.         for (int i = n - 1; i >= 0; --i) {
  73.             p[--cnt[c[pn[i]]]] = pn[i];
  74.         }
  75.         cn[p[0]] = 0;
  76.         for (int i = 1; i < n; ++i) {
  77.             cn[p[i]] = cn[p[i - 1]];
  78.             if (c[p[i]] != c[p[i - 1]]) {
  79.                 ++cn[p[i]];
  80.                 continue;
  81.             }
  82.             int x = p[i] + len;
  83.             if (x >= n) {
  84.                 x -= n;
  85.             }
  86.             int y = p[i - 1] + len;
  87.             if (y >= n) {
  88.                 y -= n;
  89.             }
  90.             if (c[x] != c[y]) {
  91.                 ++cn[p[i]];
  92.             }
  93.         }
  94.         memcpy(c, cn, sizeof(c));
  95.     }
  96.     for (int i = 0; i < n; ++i) {
  97.         pos[p[i]] = i;
  98.     }
  99.     int k = 0;
  100.     for (int i = 0; i < n; ++i) {
  101.         if (pos[i] == n - 1) {
  102.             k = 0;
  103.             continue;
  104.         }
  105.         k = max(k - 1, 0);
  106.         int j = p[pos[i] + 1];
  107.         while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
  108.             ++k;
  109.         }
  110.         lcp[pos[i]] = k;
  111.     }
  112. }
  113.  
  114. struct query {
  115.     ll k;
  116.     int id;
  117.     bool operator<(const query& other) const {
  118.         return k < other.k;
  119.     }
  120. };
  121.  
  122. void rem(ordered_set& s, int x) {
  123.     pii pp = {x, inf};
  124.     ordered_set::iterator it = s.upper_bound(pp);
  125.     --it;
  126.     int l = it->first, r = it->second;
  127.     assert(l <= x && x <= r);
  128.     s.erase(it);
  129.     if (l <= x - 1) {
  130.         s.insert({l, x - 1});
  131.     }
  132.     if (x + 1 <= r) {
  133.         s.insert({x + 1, r});
  134.     }
  135. }
  136.  
  137. void split(ordered_set& s, int z) {
  138.     pii pp = {z, inf};
  139.     ordered_set::iterator it = s.upper_bound(pp);
  140.     //cout << "!" << it->first << " " << it->second << endl;
  141.     --it;
  142.     int l = it->first, r = it->second;
  143.  
  144.     assert(l <= z && z + 1 <= r);
  145.     s.erase(it);
  146.     s.insert({l, z});
  147.     s.insert({z + 1, r});
  148. }
  149.  
  150. int getMax(int l, int r) {
  151.     int k = deg[r - l + 1];
  152.     return max(sparse[k][l], sparse[k][r - (1 << k) + 1]);
  153. }
  154.  
  155. int main() {
  156.  
  157.     ios_base::sync_with_stdio(false);
  158.     cin.tie(0);
  159.     cout.tie(0);
  160.  
  161.     //ifstream cin("input.txt");
  162.  
  163.     deg[0] = -1;
  164.     for (int i = 1; i < nmax; ++i) {
  165.         deg[i] = deg[i - 1];
  166.         if (!(i & (i - 1))) {
  167.             ++deg[i];
  168.         }
  169.     }
  170.  
  171.     string s;
  172.     cin >> s;
  173.     s += "#";
  174.     int n = sz(s);
  175.  
  176.     suffixArray(s);
  177.  
  178.     int q;
  179.     cin >> q;
  180.     vector<query> queries(q);
  181.     for (int i = 0; i < q; ++i) {
  182.         cin >> queries[i].k;
  183.         queries[i].id = i;
  184.     }
  185.     sort(all(queries));
  186.  
  187.     ordered_set setik;
  188.     int l = 1;
  189.     for (int r = 2; r < n; ++r) {
  190.         if (s[p[r]] != s[p[l]]) {
  191.             setik.insert({l, r - 1});
  192.             l = r;
  193.         }
  194.     }
  195.     setik.insert({l, n - 1});
  196.     int curLen = 1;
  197.  
  198.     ll skipped = 0;
  199.     vector<pii> ans(q, {-1, -1});
  200.  
  201.     vector<vector<int> > equalLCP(n + 1);
  202.     for (int i = 0; i < n - 1; ++i) {
  203.         equalLCP[lcp[i]].pb(i);
  204.     }
  205.  
  206.     /*for (int i = 0; i < n - 1; ++i) {
  207.         cout << lcp[i] << "\n";
  208.     }
  209.     return 0;*/
  210.  
  211.     /*for (pii pp : setik) {
  212.         cout << pp.first << " " << pp.second << endl;
  213.     }
  214.  
  215.     return 0;*/
  216.  
  217.     for (int i = 0; i < n; ++i) {
  218.         sparse[0][i] = n - p[i];
  219.     }
  220.     for (int r = 0; r + 1 < rmax; ++r) {
  221.         for (int i = 0; i < n; ++i) {
  222.             int j = min(n - 1, i + (1 << r));
  223.             sparse[r + 1][i] = max(sparse[r][i], sparse[r][j]);
  224.         }
  225.     }
  226.  
  227.     for (query Q : queries) {
  228.         Q.k -= skipped;
  229.         bool bad = false;
  230.         while (Q.k > sz(setik)) {
  231.             if (curLen == n) {
  232.                 bad = true;
  233.                 break;
  234.             }
  235.             skipped += sz(setik);
  236.             Q.k -= sz(setik);
  237.             int x = pos[n - curLen - 1];
  238.             rem(setik, x);
  239.             for (int z : equalLCP[curLen]) {
  240.                 //cout << "!" << z << endl;
  241.                 int len = n - p[z] - 1;
  242.                 if (len <= curLen) {
  243.                     continue;
  244.                 }
  245.                 len = n - p[z + 1] - 1;
  246.                 if (len <= curLen) {
  247.                     continue;
  248.                 }
  249.                 split(setik, z);
  250.             }
  251.             ++curLen;
  252.         }
  253.  
  254.         if (bad) {
  255.             continue;
  256.         }
  257.         // pp - kth pair in setik
  258.         pii pp = *(setik.find_by_order(Q.k - 1));
  259.         int l = pp.first, r = pp.second;
  260.         //cout << "!" << pp.first << " " << pp.second << endl;
  261.         int len = getMax(l, r);
  262.         ans[Q.id] = {n - len + 1, n - len + 1 + curLen - 1};
  263.         //cout << Q.id << " " << curLen << endl;
  264.         //cout << "!" << skipped << endl;
  265.     }
  266.  
  267.     for (int i = 0; i < q; ++i) {
  268.         cout << ans[i].first << " " << ans[i].second << "\n";
  269.     }
  270.  
  271. }
  272.  
Runtime error #stdin #stdout #stderr 0.01s 23984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Id1Ytz
language:
C++14 (gcc 8.3)
created:
3 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!