Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <fstream>
- #include <cstdlib>
- #include <ctime>
- #include <set>
- #include <iterator>
- #include <string>
- #include <stdio.h>
- using namespace std;
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- typedef unsigned long long ull;
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- string s;
- cin >> s;
- const int p = 31;
- const long long int big_mod = 1e9 + 9;
- vector <unsigned long long> h(s.length() + 1),
- vector <unsigned long long> deg(s.length() + 1);
- h[0] = 0, deg[0] = 1;
- for (int i = 0; i < s.length(); i++) {
- h[i + 1] = h[i] * p + s[i];
- deg[i + 1] = deg[i] * p;
- }
- auto get_hash = [&](int l, int r) {
- return h[r + 1] - h[l] * deg[r - l + 1];
- };
- int m = 0;
- cin >> m;
- int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
- int len_1 = 0, len_2 = 0, smallLen = 0, super_count = 0;
- for (int i = 0; i < m; ++i)
- {
- cin >> l1 >> r1 >> l2 >> r2;
- len_1 = r1 - l1 + 1;
- len_2 = r2 - l2 + 1;
- smallLen = min(len_1, len_2);
- super_count = 0;
- if (get_hash(l1, r1) == get_hash(l2, r2))
- {
- if (len_1 == len_2)
- cout << "0\n";
- else if (len_1 > len_2)
- cout << "1\n";
- else
- cout << "-1\n";
- }
- else
- {
- int left = 0, right = 0, middle = 0, defLen = 0, search = -1, counert = 1;
- if (len_1 < len_2)
- {
- left = l1;
- right = r1;
- counert = 1;
- }
- else
- {
- left = l2;
- right = r2;
- counert = 2;
- }
- while (left <= right)
- {
- middle = (left + right) / 2;
- if (counert == 1)
- defLen = middle - l1 + 1;
- else
- defLen = middle - l2 + 1;
- if (get_hash(l1, r1) == get_hash(l2, r2))
- {
- left = middle + 1;
- search = defLen - 1;
- }
- else
- {
- right = middle - 1;
- search = defLen - 1;
- }
- }
- //cout << search << endl;
- int last_elem = l1 + search;
- if (s[l1 + search] > s[l2 + search])
- cout << "1\n";
- else
- cout << "-1\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement