Advertisement
Guest User

Untitled

a guest
Dec 21st, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <fstream>
  7. #include <cstdlib>
  8. #include <ctime>
  9. #include <set>
  10. #include <iterator>
  11. #include <string>
  12. #include <stdio.h>
  13.  
  14. using namespace std;
  15.  
  16. ifstream fin("input.txt");
  17. ofstream fout("output.txt");
  18.  
  19. typedef unsigned long long ull;
  20.  
  21. int main()
  22. {
  23. ios_base::sync_with_stdio(false);
  24. cin.tie(NULL);
  25. string s;
  26. cin >> s;
  27. const int p = 31;
  28. const long long int big_mod = 1e9 + 9;
  29. vector <unsigned long long> h(s.length() + 1),
  30. vector <unsigned long long> deg(s.length() + 1);
  31. h[0] = 0, deg[0] = 1;
  32. for (int i = 0; i < s.length(); i++) {
  33. h[i + 1] = h[i] * p + s[i];
  34. deg[i + 1] = deg[i] * p;
  35. }
  36. auto get_hash = [&](int l, int r) {
  37. return h[r + 1] - h[l] * deg[r - l + 1];
  38. };
  39. int m = 0;
  40. cin >> m;
  41. int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
  42. int len_1 = 0, len_2 = 0, smallLen = 0, super_count = 0;
  43. for (int i = 0; i < m; ++i)
  44. {
  45. cin >> l1 >> r1 >> l2 >> r2;
  46. len_1 = r1 - l1 + 1;
  47. len_2 = r2 - l2 + 1;
  48. smallLen = min(len_1, len_2);
  49. super_count = 0;
  50. if (get_hash(l1, r1) == get_hash(l2, r2))
  51. {
  52. if (len_1 == len_2)
  53. cout << "0\n";
  54. else if (len_1 > len_2)
  55. cout << "1\n";
  56. else
  57. cout << "-1\n";
  58. }
  59. else
  60. {
  61. int left = 0, right = 0, middle = 0, defLen = 0, search = -1, counert = 1;
  62. if (len_1 < len_2)
  63. {
  64. left = l1;
  65. right = r1;
  66. counert = 1;
  67. }
  68. else
  69. {
  70. left = l2;
  71. right = r2;
  72. counert = 2;
  73. }
  74. while (left <= right)
  75. {
  76. middle = (left + right) / 2;
  77. if (counert == 1)
  78. defLen = middle - l1 + 1;
  79. else
  80. defLen = middle - l2 + 1;
  81. if (get_hash(l1, r1) == get_hash(l2, r2))
  82. {
  83. left = middle + 1;
  84. search = defLen - 1;
  85. }
  86. else
  87. {
  88. right = middle - 1;
  89. search = defLen - 1;
  90. }
  91. }
  92. //cout << search << endl;
  93. int last_elem = l1 + search;
  94. if (s[l1 + search] > s[l2 + search])
  95. cout << "1\n";
  96. else
  97. cout << "-1\n";
  98. }
  99. }
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement