Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. //<(")
  3. #define ll long long
  4. using namespace std;
  5.  
  6. const ll base = 31;
  7. const ll siz = 1e6 + 10;
  8. const ll mod = 1e9 + 7;
  9. const ll MAXX = 1e18;
  10.  
  11. ll n, m;
  12. string a, b;
  13.  
  14. ll hashVal[siz][2];
  15. ll Pow[siz];
  16.  
  17. void setup() {
  18. for (ll i = 1; i < siz; i++) {
  19. Pow[i] = (Pow[i - 1] * base) % mod;
  20. }
  21. a = ' ' + a;
  22. b = ' ' + b;
  23. for (ll i = 1; i <= n; i++) {
  24. hashVal[i][0] = (hashVal[i - 1][0] * base + a[i] - 'a' + 1) % mod;
  25. }
  26. for (ll i = 1; i <= m; i++) {
  27. hashVal[i][1] = (hashVal[i - 1][1] * base + b[i] - 'a' + 1) % mod;
  28. }
  29. }
  30.  
  31. ll getHash(ll a, ll b, bool pos) {
  32. return (hashVal[b][pos] - hashVal[a - 1][pos] * Pow[b - a + 1] + mod * mod) % mod;
  33. }
  34.  
  35. int main() {
  36. ios::sync_with_stdio(false);
  37. cin.tie(0);
  38. cout.tie(0);
  39. //freopen("INP.txt", "r", stdin);
  40. //freopen("OUT.txt", "w", stdout);
  41. cin >> n >> m;
  42. cin >> a >> b;
  43. setup();
  44. ll q;
  45. cin >> q;
  46. while (q--) {
  47. ll l, r, u, v;
  48. cin >> l >> r >> u >> v;
  49. ll x = getHash(l, r, 0), y = getHash(u, v, 1);
  50. if (x == y) {
  51. cout << '=';
  52. continue;
  53. }
  54. if ((r - l) > (v - u)) {
  55. ll le = u, ri = v;
  56. ll pos = 0;
  57. while (le <= ri) {
  58. ll mid = (le + ri) / 2;
  59. if (getHash(l, l + mid - 1, 0) == getHash(u, u + mid - 1, 1)) {
  60. le = mid + 1;
  61. }
  62. else {
  63. pos = mid;
  64. ri = mid - 1;
  65. }
  66. }
  67. if (a[pos] == b[pos]) {
  68. cout << '>';
  69. }
  70. else {
  71. if (a[pos] < b[pos]) {
  72. cout << '<';
  73. }
  74. else {
  75. cout << '>';
  76. }
  77. }
  78. }
  79. else {
  80. ll le = l, ri = r;
  81. ll pos = 0;
  82. while (le <= ri) {
  83. ll mid = (le + ri) / 2;
  84. //cerr << mid << '\n';
  85. //cerr << getHash(l, l + mid - 1, 0) << ' ' << getHash(u, u + mid - 1, 1) << '\n';
  86. if (getHash(l, l + mid - 1, 0) == getHash(u, u + mid - 1, 1)) {
  87. le = mid + 1;
  88. }
  89. else {
  90. pos = mid;
  91. ri = mid - 1;
  92. }
  93. }
  94. if (a[pos] == b[pos]) {
  95. cout << '<';
  96. }
  97. else {
  98. if (a[pos] < b[pos]) {
  99. cout << '<';
  100. }
  101. else {
  102. cout << '>';
  103. }
  104. }
  105. cerr << pos << '\n';
  106. }
  107. }
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement