Advertisement
skimono

Alena_Eklmn

Oct 26th, 2021
214
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.24 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <stack>
  7. #include <iomanip>
  8. #include <fstream>
  9. #include <string>
  10. #include <set>
  11. #include <deque>
  12. #include <queue>
  13. #include <map>
  14. #include <bitset>
  15. #include <random>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22. typedef string str;
  23. #define endl "\n"
  24. #define sqrt sqrtl
  25.  
  26. #define all(a) a.begin(), a.end();
  27. #define pow bin_pow
  28.  
  29. const ll M = 1e9 + 7, m = 998244353;
  30.  
  31. struct Hash {
  32.     ll x, z;
  33.     Hash(ll y = 0) { x = y; z = y; }
  34. };
  35.  
  36. Hash operator + (Hash a, Hash b) {
  37.     Hash c;
  38.     c.x = (a.x + b.x) % M;
  39.     c.z = (a.z + b.z) % m;
  40.     return c;
  41. }
  42. bool operator == (Hash a, Hash b) {
  43.     return a.x == b.x and a.z == b.z;
  44. }
  45. bool operator != (Hash a, Hash b) {
  46.     return a.x != b.x or a.z != b.z;
  47. }
  48. bool operator > (Hash a, Hash b) {
  49.     return a.x > b.x and a.z > b.z;
  50. }
  51. Hash operator - (Hash a, Hash b) {
  52.     Hash c;
  53.     c.x = ((a.x - b.x) % M + M) % M;
  54.     c.z = ((a.z - b.z) % m + m) % m;
  55.     return c;
  56. }
  57. Hash operator * (Hash a, Hash b) {
  58.     Hash c;
  59.     c.x = (a.x * b.x) % M;
  60.     c.z = (a.z * b.z) % m;
  61.     return c;
  62. }
  63.  
  64. Hash gethash(ll i, ll N, const vector<Hash>& hashes, const vector<Hash>& powers) {
  65.     return hashes[N + 1] - hashes[i] * powers[N - i + 1];
  66. }
  67.  
  68. Hash f_hashes(vector<Hash>& hashes, str a, ll p) {
  69.     for (ll i = 0; i < (ll)a.size(); i++) {
  70.         hashes[i + 1] = hashes[i] * p + a[i];
  71.     }
  72.     return hashes[a.size()];
  73. }
  74.  
  75. void f_powers(vector<Hash>& powers, ll p, ll n) {
  76.     for (ll i = 0; i < n; i++) {
  77.         powers[i + 1] = powers[i] * p;
  78.     }
  79. }
  80.  
  81. signed main() {
  82. #ifdef _DEBUG
  83.     freopen("input.txt", "r", stdin);
  84.     freopen("output.txt", "w", stdout);
  85. #endif
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(NULL);
  88.     cout.tie(NULL);
  89.     str a, b;
  90.     cin >> a;
  91.     ll p = 239, ans1 = 0, n, N;
  92.     n = a.size();
  93.     b = a;
  94.     reverse(b.begin(), b.end());
  95.     vector<Hash> hashes(n + 1), powers(n + 1), hashes_b(n + 1);
  96.     //ll ans = n;
  97.     powers[0] = 1;
  98.     ll t;
  99.     cin >> t;
  100.     //ans1 = f_hashes(hashes, b, p).x;
  101.     f_hashes(hashes, a, p);
  102.     f_powers(powers, p, (ll)a.size());
  103.  
  104.     for (ll i = 0; i < t; i++) {
  105.         ll x1, x2, y1, y2;
  106.         cin >> x1 >> y1 >> x2 >> y2;
  107.         //x1--;
  108.         //x2--;
  109.         y1++;
  110.         y2++;
  111.         ll q = x2 - x1;
  112.         ll h = min(y1 - x1, y2 - x2);
  113.         ll l = x1 - 1, r = x1 + h + 1;
  114.         while (l + 1 < r) {
  115.             ll MM = (l + r) / 2;
  116.             if (gethash(x1, MM, hashes, powers) != gethash(x2, MM + q, hashes, powers)) {
  117.                 r = MM;
  118.             }
  119.             else {
  120.                 l = MM;
  121.             }
  122.         }
  123.         if (l >= x1 + h - 1) {
  124.             if (y1 - x1 == y2 - x2)
  125.                 cout << "=" << endl;
  126.             else if (y1 - x1 < y2 - x2) {
  127.                 cout << "<" << endl;
  128.             }
  129.             else {
  130.                 cout << ">" << endl;
  131.             }
  132.         }
  133.         else if (gethash(x1, r, hashes, powers) > gethash(x2, r + q, hashes, powers)) {
  134.             cout << ">" << endl;
  135.         }
  136.         else {
  137.             cout << "<" << endl;
  138.         }
  139.     }
  140.     return 0;
  141. }
  142.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement