Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <fstream>
- #include <vector>
- using namespace std;
- using lint = long long;
- lint power (lint a, lint b, lint mod) {
- if (b == 0) {
- return 1;
- }
- lint ans = power(a, b / 2, mod);
- if (b % 2) {
- return (ans * ((ans * a) % mod)) % mod;
- } else {
- return (ans * ans) % mod;
- }
- }
- const vector<lint> rand_primes = {500757157, 667851013, 801413363, 836971151,
- 659598383, 660567227, 891749389, 504890891,
- 535766299, 526239611};
- struct Mods {
- vector<pair<lint, lint>> primes;
- vector<vector<int>> primespows;
- Mods(int n) {
- primes.resize(n);
- primespows.resize(n);
- for (int i = 0; i < n; i++) {
- primes[i].first = rand_primes[2 * i];
- primes[i].second = rand_primes[2 * i + 1];
- primespows[i].push_back(1);
- for (int j = 1; j <= 1e5; j++) {
- primespows[i].push_back((primespows[i].back() * primes[i].first) % primes[i].second);
- }
- }
- }
- };
- struct Hash {
- string str;
- vector<vector<lint>> prefhashes;
- Hash(string& str_, Mods& t): str(str_) {
- int n = t.primes.size();
- prefhashes.resize(n, vector<lint>(str.size() + 1));
- for (int i = 0; i < n; i++) {
- for (int j = 1; j <= (int)str.size(); j++) {
- prefhashes[i][j] = static_cast<lint>(str[j - 1]) + t.primes[i].first * prefhashes[i][j - 1];
- prefhashes[i][j] %= t.primes[i].second;
- }
- }
- }
- };
- bool isequal (Hash& h1, int l1, int r1, Hash& h2, int l2, int r2, Mods& t) {
- //cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
- if (r1 - l1 != r2 - l2) {
- return true;
- }
- for (int i = 0; i < (int)h1.prefhashes.size(); i++) {
- lint fir = (h1.prefhashes[i][r1 + 1] + (t.primes[i].second - t.primespows[i][r1 - l1 + 1])
- * h1.prefhashes[i][l1]) % t.primes[i].second;
- lint sec = (h2.prefhashes[i][r2 + 1] + (t.primes[i].second - t.primespows[i][r1 - l1 + 1])
- * h2.prefhashes[i][l2]) % t.primes[i].second;
- //cout << fir << " " << sec << endl;
- if (fir != sec) {
- return false;
- }
- }
- return true;
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- string s;
- cin >> s;
- Mods make_hash(1);
- Hash h1(s, make_hash);
- int n;
- cin >> n;
- /*for (auto &x : h1.prefhashes) {
- for (auto &y : x) {
- cout << y << " ";
- }
- cout << endl;
- }*/
- //cout << power(2, 3, 9) << endl;
- //cout << power(3, 2, 9) << endl;
- for (lint i = 0; i < n; i++) {
- lint l1, r1, l2, r2;
- cin >> l1 >> r1 >> l2 >> r2;
- if (i == 500000) {
- cout << 1/0 << endl;
- }
- lint lef = 0;
- lint rig = min(r1 - l1, r2 - l2) + 2;
- while (rig - lef > 1) {
- lint mid = (lef + rig) / 2;
- //cout << mid << endl;
- if (isequal(h1, l1, l1 + mid - 1, h1, l2, l2 + mid - 1, make_hash)) {
- //cout << "ok" << endl;
- lef = mid;
- } else {
- //cout << "notok" << endl;
- rig = mid;
- }
- }
- //cout << lef << endl;
- int ans = 0;
- if (lef == r1 - l1 + 1) {
- if (lef == r2 - l2 + 1) {
- ans = 0;
- } else {
- ans = -1;
- }
- } else {
- if (lef == r1 - l1 + 1) {
- ans = 1;
- } else {
- if (s[l1 + lef] > s[l2 + lef]) {
- ans = 1;
- } else {
- ans = -1;
- }
- }
- }
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement