Advertisement
playerr17

Untitled

Dec 26th, 2022
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.48 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize ("unroll-loops")
  3. //#pragma GCC optimize ("fast-math")
  4. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #include <bits/stdc++.h>
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <string>
  10. #include <cmath>
  11. #include <vector>
  12. #include <map>
  13. #include <set>
  14. #include <list>
  15. #include <ctime>
  16. #include <stack>
  17. #include <queue>
  18. #include <iomanip>
  19. #include <cstdlib>
  20. #include <unordered_map>
  21. #include <unordered_set>
  22. #include <cstddef>
  23. #include <deque>
  24. #include <cstdio>
  25. #include <fstream>
  26. #include <random>
  27. #include <climits>
  28.  
  29. using namespace std;
  30. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  31. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  32. #define pb push_back
  33. #define mp make_pair
  34. #define f first
  35. #define s second
  36. #define all(x) begin(x), end(x)
  37. #define sz(a) ((int)((a).size()))
  38. #define endl '\n'
  39. const long long INF = 1e18+1;
  40. const long double EPS = 1e-9;
  41. typedef long long ll;
  42. typedef unsigned long long ull;
  43. typedef long double ld;
  44. //std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
  45. #define dbg(x) cerr << #x << " = " << x << '\n';
  46.  
  47. const int MOD = 1e9 + 7, MOD1 = 998244353;
  48. const int P = 29;
  49.  
  50. ull H[100100], step[100100];
  51. ull H1[100100], step1[100100];
  52. string s;
  53.  
  54. ull get_hash(int l, int r){
  55.     if (l == 0) {
  56.         return H[r];
  57.     }
  58.     return ((1LL * H[r] - (1LL * H[l - 1] * step[r - l + 1]) % MOD) % MOD + MOD) % MOD;
  59. }
  60.  
  61. ull get_hash1(int l, int r){
  62.     if (l == 0) {
  63.         return H1[r];
  64.     }
  65.     return ((1LL * H1[r] - (1LL * H1[l - 1] * step1[r - l + 1]) % MOD1) % MOD1 + MOD1) % MOD1;
  66. }
  67.  
  68. struct substr{
  69.     int i, len;
  70.  
  71.     substr (int i_, int len_) : i(i_), len(len_) {
  72.     }
  73.  
  74.     bool operator> (substr b) {
  75.         int mi = -1, ma = min(len, b.len);
  76.         while(mi + 1 < ma){
  77.             int sr = (mi + ma) / 2;
  78. //            int a = get_hash(i, i + sr), b1 =  get_hash(b.i, b.i + sr), c = get_hash1(i, i + sr), d = get_hash1(b.i, b.i + sr);
  79.             if(get_hash(i, i + sr) == get_hash(b.i, b.i + sr) && get_hash1(i, i + sr) == get_hash1(b.i, b.i + sr)) mi = sr;
  80.             else ma = sr;
  81.         }
  82.         if(mi == min(len, b.len) - 1) return len > b.len;
  83.         else {
  84.             assert(s[i + mi + 1] != s[b.i + mi + 1]);
  85.             return s[i + mi + 1] > s[b.i + mi + 1];
  86.         }
  87.     }
  88. };
  89.  
  90. void solve() {
  91.     cin >> s;
  92.     int n = sz(s);
  93.     step[0] = 1;
  94.     forn1(i, 1, n) step[i] = (1LL * step[i - 1] * 37) % MOD;
  95.     H[0] = s[0] - 'a';
  96.     forn(i, 1, n) H[i] = ((1LL * H[i - 1] * 37) % MOD + 1LL * (s[i] - 'a')) % MOD;
  97.     step1[0] = 1;
  98.     forn1(i, 1, n) step1[i] = (1LL * step1[i - 1] * 103) % MOD1;
  99.     H1[0] = s[0] - 'a';
  100.     forn(i, 1, n) H1[i] = ((1LL * H1[i - 1] * 103) % MOD1 + 1LL * (s[i] - 'a')) % MOD1;
  101. //    dbg(get_hash1(4, 6));
  102.     int q;
  103.     cin >> q;
  104.     while (q--) {
  105.         int l1, r1, l2, r2;
  106.         cin >> l1 >> r1 >> l2 >> r2; l1--; l2--; r1--; r2--;
  107.         substr lhs(l1, r1 - l1 + 1), rhs(l2, r2 - l2 + 1);
  108.         if (lhs > rhs) {
  109.             cout << ">" << endl;
  110.         } else if (rhs > lhs) {
  111.             cout << "<" << endl;
  112.         } else {
  113.             cout << "=" << endl;
  114.         }
  115.     }
  116. }
  117.  
  118. int32_t main()
  119. {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(NULL);
  122.     cout.tie(NULL);
  123.     cout.precision(30);
  124.     int t = 1;
  125.     while (t--) {
  126.         solve();
  127.     }
  128.     return 0;
  129. }
  130.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement