Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- #define endl "\n"
- #define sqrt sqrtl
- #define all(a) a.begin(), a.end();
- #define pow bin_pow
- const ll M = 1e9 + 7, m = 998244353;
- struct Hash {
- ll x, z;
- Hash(ll y = 0) { x = y; z = y; }
- };
- Hash operator + (Hash a, Hash b) {
- Hash c;
- c.x = (a.x + b.x) % M;
- c.z = (a.z + b.z) % m;
- return c;
- }
- bool operator == (Hash a, Hash b) {
- return a.x == b.x and a.z == b.z;
- }
- bool operator != (Hash a, Hash b) {
- return a.x != b.x or a.z != b.z;
- }
- bool operator > (Hash a, Hash b) {
- return a.x > b.x and a.z > b.z;
- }
- Hash operator - (Hash a, Hash b) {
- Hash c;
- c.x = ((a.x - b.x) % M + M) % M;
- c.z = ((a.z - b.z) % m + m) % m;
- return c;
- }
- Hash operator * (Hash a, Hash b) {
- Hash c;
- c.x = (a.x * b.x) % M;
- c.z = (a.z * b.z) % m;
- return c;
- }
- Hash gethash(ll i, ll N, const vector<Hash>& hashes, const vector<Hash>& powers) {
- return hashes[N + 1] - hashes[i] * powers[N - i + 1];
- }
- Hash f_hashes(vector<Hash>& hashes, str a, ll p) {
- for (ll i = 0; i < (ll)a.size(); i++) {
- hashes[i + 1] = hashes[i] * p + a[i];
- }
- return hashes[a.size()];
- }
- void f_powers(vector<Hash>& powers, ll p, ll n) {
- for (ll i = 0; i < n; i++) {
- powers[i + 1] = powers[i] * p;
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- str a, b;
- cin >> a;
- ll p = 239, ans1 = 0, n, N;
- n = a.size();
- b = a;
- reverse(b.begin(), b.end());
- vector<Hash> hashes(n + 1), powers(n + 1), hashes_b(n + 1);
- //ll ans = n;
- powers[0] = 1;
- ll t;
- cin >> t;
- //ans1 = f_hashes(hashes, b, p).x;
- f_hashes(hashes, a, p);
- f_powers(powers, p, (ll)a.size());
- for (ll i = 0; i < t; i++) {
- ll x1, x2, y1, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- //x1--;
- //x2--;
- y1++;
- y2++;
- ll q = x2 - x1;
- ll h = min(y1 - x1, y2 - x2);
- ll l = x1 - 1, r = x1 + h + 1;
- while (l + 1 < r) {
- ll MM = (l + r) / 2;
- if (gethash(x1, MM, hashes, powers) != gethash(x2, MM + q, hashes, powers)) {
- r = MM;
- }
- else {
- l = MM;
- }
- }
- if (l >= x1 + h - 1) {
- if (y1 - x1 == y2 - x2)
- cout << "=" << endl;
- else if (y1 - x1 < y2 - x2) {
- cout << "<" << endl;
- }
- else {
- cout << ">" << endl;
- }
- }
- else if (gethash(x1, r, hashes, powers) > gethash(x2, r + q, hashes, powers)) {
- cout << ">" << endl;
- }
- else {
- cout << "<" << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement