Oscar2019

Untitled

Sep 21st, 2020
738
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #ifndef ONLINE_JUDGE
  6.     #define W(x, y) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << y;
  7. #else
  8.     #define W(x, y)
  9. #endif
  10.  
  11. using ll = long long;
  12. using pii = pair<int, int>;
  13. using pll = pair<ll, ll>;
  14. using vi = vector<int>;
  15. using vii = vector<pii>;
  16. using vl = vector<ll>;
  17. using vll = vector<pll>;
  18. using ld = long double;
  19. #define ff first
  20. #define ss second
  21. const ld pi = acosl(-1);
  22. const ll prime = 1000000000 + 7;
  23. const ll INF = 1000000000;
  24.  
  25. template<typename F>
  26. void countsort(vl &ind, F f){
  27.     ll n = ind.size();
  28.     vl cnt(n);
  29.     vl pos(n);
  30.     vl vet_ans(n);
  31.     for(int i = 0; i < n; ++i){
  32.         cnt[f(ind[i])]++;
  33.     }
  34.     for(int i = 1; i < n; ++i){
  35.         pos[i] = pos[i-1] + cnt[i-1];
  36.     }
  37.     for(int i = 0; i < n; ++i){
  38.         ll aux = f(ind[i]);
  39.         vet_ans[pos[aux]] = ind[i];
  40.         pos[aux]++;
  41.     }
  42.     ind = vet_ans;
  43. }
  44.  
  45. struct SparceTable{
  46.     ll n;
  47.     ll m;
  48.     vector<vl> mat;
  49.     vl mylog;
  50.     SparceTable(){
  51.        
  52.     }
  53.  
  54.     void init(vl &vet) {
  55.         n = vet.size();
  56.         m = 0;
  57.         while ((1 << m) <= vet.size()){
  58.             m++;
  59.         }
  60.         mat.resize(m, vl(n));
  61.         mylog.resize(n);
  62.         mat[0] = vet;
  63.         for(int i = 1; i < m; ++i){
  64.             for(int j = 0; j < n; ++j){
  65.                 if(j+(1 << (i - 1)) < n){
  66.                     mat[i][j] = min(mat[i-1][j], mat[i-1][j+(1 << (i - 1))]);
  67.                 }
  68.             }
  69.         }
  70.     }
  71.     ll query(ll l, ll r){
  72.         ll res = mat[0][l];
  73.         for(int i = m-1; i >= 0; --i){
  74.             if(l <= r && (r-l+1) >= (1<<i)){
  75.                 res = min(res, mat[i][l]);
  76.                 l += 1 << i;
  77.             }
  78.         }
  79.         return res;
  80.     }
  81. };
  82.  
  83. struct SufixArray{
  84.     vl ind; // ordem do menor para o maior
  85.     vl val;
  86.     vl prefix_c;
  87.     string s;
  88.     ll n;
  89.     SparceTable st;
  90.    
  91.     void init(string &t){
  92.         s = t + '$';
  93.         n = s.size();
  94.         ind.resize(n);
  95.         val.resize(n);
  96.         prefix_c.resize(n);
  97.         iota(ind.begin(), ind.end(), 0);
  98.         sort(ind.begin(), ind.end(), [this](ll a, ll b){
  99.             return s[a] < s[b];
  100.         });
  101.         val[ind[0]] = 0;
  102.         for(int i = 1; i < n; ++i){
  103.             val[ind[i]] = val[ind[i-1]];
  104.             if(s[ind[i]] != s[ind[i-1]]){
  105.                 val[ind[i]]++;
  106.             }
  107.         }
  108.         for(int z = 0; (1LL << z) <= n; ++z){
  109.             int y = (1LL << z);
  110.             countsort(ind, [&y, this](ll x){
  111.                 return val[(x - y + 4 * n)%n];
  112.             });
  113.  
  114.             vll tmp(n);
  115.             for(int i = 0; i < n; ++i){
  116.                 ll aux1 = (ind[i] - y + 4 * n)%n;
  117.                 ll aux2 = ind[i];
  118.                 tmp[i] = {val[aux1], val[aux2]};
  119.                 ind[i] = aux1;
  120.             }
  121.  
  122.             val[ind[0]] = 0;
  123.             for(int i = 1; i < n; ++i){
  124.                 val[ind[i]] = val[ind[i-1]];
  125.                 if(tmp[ind[i]] != tmp[ind[i-1]]){
  126.                     val[ind[i]]++;
  127.                 }
  128.             }
  129.         }
  130.  
  131.         int k = 0;
  132.         for(int i = 0; i < n; ++i){
  133.             ll p = val[i]; // Qual posição o i está
  134.             if(p == 0){
  135.                 continue;
  136.             }
  137.             ll j = ind[p-1]; // vou para posição p-1 e pergunto qual o indice do primeiro caractere
  138.             while(s[i+k] == s[j+k]){
  139.                 k++;
  140.             }
  141.             prefix_c[p] = k;
  142.             k = max(k-1, 0);
  143.         }
  144.         st.init(prefix_c);
  145.     }
  146.  
  147.     ll prefixComum(ll a, ll b){
  148.         return st.query(val[a]+1, val[b]);
  149.     }
  150.    
  151. };
  152.  
  153.  
  154. int main(){
  155.     ios::sync_with_stdio(false);
  156.     cin.tie(0); cout.tie(0);
  157.  
  158.     string s;
  159.     cin >> s;
  160.     ll n = s.size();
  161.     ll m;
  162.     cin >> m;
  163.     vll vet(m);
  164.     for(int i = 0; i < m; ++i){
  165.         cin >> vet[i].ff >> vet[i].ss;
  166.     }
  167.     SufixArray sa;
  168.     sa.init(s);
  169.     sort(vet.begin(), vet.end(), [&sa](pll a, pll b){
  170.         a.ff--;
  171.         a.ss--;
  172.         b.ff--;
  173.         b.ss--;
  174.         ll ta = a.ss-a.ff+1;
  175.         ll tb = b.ss-b.ff+1;
  176.         ll k = sa.prefixComum(a.ff, b.ff);
  177.         if(k >= ta && k >= tb){
  178.             if(ta == tb){
  179.                 return a < b;
  180.             } else{
  181.                 return ta < tb;
  182.             }
  183.         } else if(k >= ta){
  184.             return ta < tb;
  185.         } else if(k >= tb){
  186.             return ta < tb;
  187.         } else{
  188.             return sa.s[a.ff + k] < sa.s[b.ff + k];
  189.         }
  190.     });
  191.     cerr << endl;
  192.     for(int i = 0; i < m; ++i){
  193.         cout << vet[i].ff << " " << vet[i].ss <<  "\n";
  194.     }
  195.  
  196.     return 0;
  197. }
RAW Paste Data