fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fu(i, a, b) for (int i = a; i <= b; i++)
  5. #define int long long
  6. #define task "test"
  7.  
  8. const int MAXN = 1e6 + 5;
  9. const int MOD = 1e9 + 7;
  10. const int BASE = 35;
  11. string a,b;
  12. int HASHA[MAXN], HASHB[MAXN], BASEPOW[MAXN];
  13. int lenA, lenB;
  14. int q;
  15.  
  16. int getA(int l, int r) {
  17.     return (HASHA[r] - HASHA[l - 1] * BASEPOW[r - l + 1] % MOD + MOD) % MOD;
  18. }
  19. int getB(int l, int r) {
  20.     return (HASHB[r] - HASHB[l - 1] * BASEPOW[r - l + 1] % MOD + MOD) % MOD;
  21. }
  22.  
  23.  
  24. void init() {
  25.     cin >> lenA >> lenB >> a >> b >> q;
  26.     BASEPOW[0] = 1;
  27.     int MAX = 1e6;
  28.     fu(i,1,MAX) BASEPOW[i] = (BASEPOW[i-1]*BASE)%MOD;
  29.     a = "&" + a, b = "&" + b;
  30.     fu(i,1,lenA) HASHA[i] = (HASHA[i-1]*BASE + (a[i] - 'a' + 1))%MOD;
  31.     fu(i,1,lenB) HASHB[i] = (HASHB[i-1]*BASE + (b[i] - 'a' + 1))%MOD;
  32. }
  33.  
  34. void solve() {
  35.     while(q--) {
  36.         int l,r,u,v; cin >> l >> r >> u >> v;
  37.         int len1 = r - l + 1, len2 = v - u + 1;
  38.         int len = min(len1, len2), ans = 0;
  39.         int left = 0, right = len;
  40.         while(left<=right) {
  41.             int mid = (left + right) / 2;
  42.             if(getA(l,l+mid-1) == getB(u, u+mid-1)) {
  43.                 ans = mid;
  44.                 left = mid + 1;
  45.             }
  46.             else right = mid - 1;
  47.         }
  48.         if (ans == len) {
  49.             if (len1 == len2) cout << "=";
  50.             else if (len1 < len2) cout << "<";
  51.             else cout << ">";
  52.         } 
  53.         else {
  54.             char chA = a[l + ans], chB = b[u + ans];
  55.             if (chA > chB) cout << ">";
  56.             else if (chA < chB) cout << "<";
  57.             else cout << "="; 
  58.         }
  59.     }
  60. }
  61.  
  62. signed main() {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(NULL);
  65.     if (fopen(task ".inp", "r")) freopen(task ".inp", "r", stdin), freopen(task ".out", "w", stdout);
  66.     init();
  67.     solve();
  68. }
  69.  
Success #stdin #stdout 0.01s 11544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0CbbU6
language:
C++14 (gcc 8.3)
created:
72 days ago
visibility:
secret

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!