fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pub push_back
  3. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  4. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define all(x) begin(x), end(x)
  9. #define int long long
  10. using namespace std;
  11.  
  12. const int N = 1e6 + 5;
  13. const int M = 1e6 + 5;
  14. const int mod1 = 2e9 + 11;
  15. const int mod2 = 1e9 + 7;
  16. const int inf = 1e18;
  17.  
  18. int n, m, q;
  19. pii base[N], fa[N], fb[N];
  20. string a, b;
  21.  
  22. int mulMod(int a, int b, int mod) {
  23.     return (a * b) % mod;
  24. }
  25. int minusMod(int a, int b, int mod) {
  26.     return ((a - b) % mod + mod) % mod;
  27. }
  28. void calBase() {
  29.     base[0].fi = 1;
  30.     base[0].se = 1;
  31.     FOR(i, 1, max(n, m), 1) {
  32.         base[i].fi = (base[i - 1].fi * 256) % mod1;
  33.         base[i].se = (base[i - 1].se * 256) % mod2;
  34.     }
  35. }
  36. void hashing(string s, int n, pii *f) {
  37.     f[0].fi = 0;
  38.     f[0].se = 0;
  39.     FOR(i, 1, n, 1) {
  40.         f[i].fi = (f[i - 1].fi * 256 + s[i]) % mod1;
  41.         f[i].se = (f[i - 1].se * 256 + s[i]) % mod2;
  42.     }
  43. }
  44. pii getHash(int l, int r, pii *f) {
  45.     int x = minusMod(f[r].fi, mulMod(f[l - 1].fi, base[r - l + 1].fi, mod1), mod1);
  46.     int y = minusMod(f[r].se, mulMod(f[l - 1].se, base[r - l + 1].se, mod2), mod2);
  47.     return {x, y};
  48. }
  49. void input() {
  50.     cin >> n >> m;
  51.     cin >> a >> b;
  52.     a.insert(0, " ");
  53.     b.insert(0, " ");
  54.     calBase();
  55.     hashing(a, n, fa);
  56.     hashing(b, m, fb);
  57. }
  58. void solve() {
  59.     input();
  60.     cin >> q;
  61.     while(q --) {
  62.         int l1, r1, l2, r2;
  63.         cin >> l1 >> r1 >> l2 >> r2;
  64.  
  65.         int lenA = r1 - l1 + 1;
  66.         int lenB = r2 - l2 + 1;
  67.  
  68.  
  69.         int low = 1;
  70.         int high = min(lenA, lenB);
  71.         int lcp = 0; //longest common prefix (dãy con tiền tố dài nhất)
  72.  
  73.         while(low <= high) {
  74.             int mid = (low + high) >> 1;
  75.             if (getHash(l1, l1 + mid - 1, fa) == getHash(l2, l2 + mid - 1, fb)) {
  76.                 lcp = mid;
  77.                 low = mid + 1;
  78.             }
  79.             else high = mid - 1;
  80.         }
  81.  
  82.  
  83.         if (l1 + lcp - 1 == r1 && l2 + lcp - 1 == r2) {
  84.             cout << "=";
  85.         }
  86.         else {
  87.             if (l1 + lcp - 1 < r1 && l2 + lcp - 1 == r2) {
  88.                 cout << ">";
  89.             }
  90.             else if (l1 + lcp - 1 == r1 && l2 + lcp - 1 < r2) {
  91.                 cout << "<";
  92.             }
  93.             else {
  94.                 if (a[l1 + lcp] > b[l2 + lcp]) {
  95.                     cout << ">";
  96.                 }
  97.                 else {
  98.                     cout << "<";
  99.                 }
  100.             }
  101.         }
  102.     }
  103. }
  104. signed main() {
  105.     #define name "baitap"
  106.     if (ifstream(name".inp")) {
  107.         freopen(name".inp", "r", stdin);
  108.         freopen(name".out", "w", stdout);
  109.     }
  110.  
  111.     ios_base::sync_with_stdio(0); 
  112.     cin.tie(0); 
  113.     cout.tie(0);
  114.  
  115.     solve();
  116. }
  117.  
Success #stdin #stdout 0.01s 7692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GIcDyB
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!