Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <fstream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. using lint = long long;
  9.  
  10. lint power (lint a, lint b, lint mod) {
  11. if (b == 0) {
  12. return 1;
  13. }
  14. lint ans = power(a, b / 2, mod);
  15. if (b % 2) {
  16. return (ans * ((ans * a) % mod)) % mod;
  17. } else {
  18. return (ans * ans) % mod;
  19. }
  20. }
  21.  
  22. const vector<lint> rand_primes = {500757157, 667851013, 801413363, 836971151,
  23. 659598383, 660567227, 891749389, 504890891,
  24. 535766299, 526239611};
  25.  
  26. struct Mods {
  27. vector<pair<lint, lint>> primes;
  28. vector<vector<int>> primespows;
  29. Mods(int n) {
  30. primes.resize(n);
  31. primespows.resize(n);
  32. for (int i = 0; i < n; i++) {
  33. primes[i].first = rand_primes[2 * i];
  34. primes[i].second = rand_primes[2 * i + 1];
  35. primespows[i].push_back(1);
  36. for (int j = 1; j <= 1e5; j++) {
  37. primespows[i].push_back((primespows[i].back() * primes[i].first) % primes[i].second);
  38. }
  39. }
  40. }
  41. };
  42.  
  43. struct Hash {
  44. string str;
  45. vector<vector<lint>> prefhashes;
  46. Hash(string& str_, Mods& t): str(str_) {
  47. int n = t.primes.size();
  48. prefhashes.resize(n, vector<lint>(str.size() + 1));
  49. for (int i = 0; i < n; i++) {
  50. for (int j = 1; j <= (int)str.size(); j++) {
  51. prefhashes[i][j] = static_cast<lint>(str[j - 1]) + t.primes[i].first * prefhashes[i][j - 1];
  52. prefhashes[i][j] %= t.primes[i].second;
  53. }
  54. }
  55. }
  56. };
  57.  
  58. bool isequal (Hash& h1, int l1, int r1, Hash& h2, int l2, int r2, Mods& t) {
  59. //cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
  60. if (r1 - l1 != r2 - l2) {
  61. return true;
  62. }
  63. for (int i = 0; i < (int)h1.prefhashes.size(); i++) {
  64. lint fir = (h1.prefhashes[i][r1 + 1] + (t.primes[i].second - t.primespows[i][r1 - l1 + 1])
  65. * h1.prefhashes[i][l1]) % t.primes[i].second;
  66. lint sec = (h2.prefhashes[i][r2 + 1] + (t.primes[i].second - t.primespows[i][r1 - l1 + 1])
  67. * h2.prefhashes[i][l2]) % t.primes[i].second;
  68. //cout << fir << " " << sec << endl;
  69. if (fir != sec) {
  70. return false;
  71. }
  72. }
  73. return true;
  74. }
  75.  
  76. int main()
  77. {
  78. ios::sync_with_stdio(0);
  79. cin.tie(0);
  80. cout.tie(0);
  81. string s;
  82. cin >> s;
  83. Mods make_hash(1);
  84. Hash h1(s, make_hash);
  85. int n;
  86. cin >> n;
  87. /*for (auto &x : h1.prefhashes) {
  88. for (auto &y : x) {
  89. cout << y << " ";
  90. }
  91. cout << endl;
  92. }*/
  93. //cout << power(2, 3, 9) << endl;
  94. //cout << power(3, 2, 9) << endl;
  95. for (lint i = 0; i < n; i++) {
  96. lint l1, r1, l2, r2;
  97. cin >> l1 >> r1 >> l2 >> r2;
  98. if (i == 500000) {
  99. cout << 1/0 << endl;
  100. }
  101. lint lef = 0;
  102. lint rig = min(r1 - l1, r2 - l2) + 2;
  103. while (rig - lef > 1) {
  104. lint mid = (lef + rig) / 2;
  105. //cout << mid << endl;
  106. if (isequal(h1, l1, l1 + mid - 1, h1, l2, l2 + mid - 1, make_hash)) {
  107. //cout << "ok" << endl;
  108. lef = mid;
  109. } else {
  110. //cout << "notok" << endl;
  111. rig = mid;
  112. }
  113. }
  114. //cout << lef << endl;
  115. int ans = 0;
  116. if (lef == r1 - l1 + 1) {
  117. if (lef == r2 - l2 + 1) {
  118. ans = 0;
  119. } else {
  120. ans = -1;
  121. }
  122. } else {
  123. if (lef == r1 - l1 + 1) {
  124. ans = 1;
  125. } else {
  126. if (s[l1 + lef] > s[l2 + lef]) {
  127. ans = 1;
  128. } else {
  129. ans = -1;
  130. }
  131. }
  132. }
  133. cout << ans << endl;
  134. }
  135.  
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement