Advertisement
MathQ_

Untitled

Dec 26th, 2022
878
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. const int mod = 1e9 + 7;
  2. const int p1 = 59, p2 = 239;
  3.  
  4. vector<ll> h1, deg1;
  5. vector<ull> h2, deg2;
  6.  
  7. ll get_hash1(int l, int r) {
  8.     return ((h1[r] - h1[l] * deg1[r - l]) % mod + mod) % mod;
  9. }
  10.  
  11. ull get_hash2(int l, int r) {
  12.     return h2[r] - h2[l] * deg2[r - l];
  13. }
  14.  
  15. bool equal(int l1, int r1, int l2, int r2) {
  16.     return get_hash1(l1 - 1, r1) == get_hash1(l2 - 1, r2) and
  17.            get_hash2(l1 - 1, r1) == get_hash2(l2 - 1, r2);
  18. }
  19.  
  20.  
  21. int main() {
  22.     string s;
  23.     cin >> s;
  24.     int n = sz(s);
  25.     deg1.resize(n + 1, 1); deg2.resize(n + 1, 1); h1.resize(n + 1); h2.resize(n + 1);
  26.     for (int i = 0; i < sz(s); ++i) {
  27.         deg1[i + 1] = deg1[i] * p1 % mod;
  28.         deg2[i + 1] = deg2[i] * p2;
  29.         h1[i + 1] = (h1[i] * p1 + s[i]) % mod;
  30.         h2[i + 1] = h2[i] * p2 + s[i];
  31.     }
  32.     int q;
  33.     cin >> q;
  34.     while (q--) {
  35.         int l1, l2, r1, r2;
  36.         cin >> l1 >> r1 >> l2 >> r2;
  37.         int l = -1, r = min(r1 - l1, r2 - l2) + 1;
  38.         while (r - l > 1) {
  39.             int m = l + r >> 1;
  40.             if (equal(l1, l1 + m, l2, l2 + m)) {
  41.                 l = m;
  42.             } else {
  43.                 r = m;
  44.             }
  45.         }
  46.         if (l == max(r1 - l1, r2 - l2)) {
  47.             cout << "=\n";
  48.         } else if (l == r2 - l2) {
  49.             cout << ">\n";
  50.         } else if (l == r1 - l1) {
  51.             cout << "<\n";
  52.         } else {
  53.             cout << (s[l1 + l] > s[l2 + l] ? ">" : "<") << '\n';
  54.         }
  55.  
  56.     }
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement