Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC optimize ("fast-math")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <list>
- #include <ctime>
- #include <stack>
- #include <queue>
- #include <iomanip>
- #include <cstdlib>
- #include <unordered_map>
- #include <unordered_set>
- #include <cstddef>
- #include <deque>
- #include <cstdio>
- #include <fstream>
- #include <random>
- #include <climits>
- using namespace std;
- #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
- #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- #define all(x) begin(x), end(x)
- #define sz(a) ((int)((a).size()))
- #define endl '\n'
- const long long INF = 1e18+1;
- const long double EPS = 1e-9;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- //std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
- #define dbg(x) cerr << #x << " = " << x << '\n';
- const int MOD = 1e9 + 7, MOD1 = 998244353;
- const int P = 29;
- ull H[100100], step[100100];
- ull H1[100100], step1[100100];
- string s;
- ull get_hash(int l, int r){
- if (l == 0) {
- return H[r];
- }
- return ((1LL * H[r] - (1LL * H[l - 1] * step[r - l + 1]) % MOD) % MOD + MOD) % MOD;
- }
- ull get_hash1(int l, int r){
- if (l == 0) {
- return H1[r];
- }
- return ((1LL * H1[r] - (1LL * H1[l - 1] * step1[r - l + 1]) % MOD1) % MOD1 + MOD1) % MOD1;
- }
- struct substr{
- int i, len;
- substr (int i_, int len_) : i(i_), len(len_) {
- }
- bool operator> (substr b) {
- int mi = -1, ma = min(len, b.len);
- while(mi + 1 < ma){
- int sr = (mi + ma) / 2;
- // int a = get_hash(i, i + sr), b1 = get_hash(b.i, b.i + sr), c = get_hash1(i, i + sr), d = get_hash1(b.i, b.i + sr);
- if(get_hash(i, i + sr) == get_hash(b.i, b.i + sr) && get_hash1(i, i + sr) == get_hash1(b.i, b.i + sr)) mi = sr;
- else ma = sr;
- }
- if(mi == min(len, b.len) - 1) return len > b.len;
- else {
- assert(s[i + mi + 1] != s[b.i + mi + 1]);
- return s[i + mi + 1] > s[b.i + mi + 1];
- }
- }
- };
- void solve() {
- cin >> s;
- int n = sz(s);
- step[0] = 1;
- forn1(i, 1, n) step[i] = (1LL * step[i - 1] * 37) % MOD;
- H[0] = s[0] - 'a';
- forn(i, 1, n) H[i] = ((1LL * H[i - 1] * 37) % MOD + 1LL * (s[i] - 'a')) % MOD;
- step1[0] = 1;
- forn1(i, 1, n) step1[i] = (1LL * step1[i - 1] * 103) % MOD1;
- H1[0] = s[0] - 'a';
- forn(i, 1, n) H1[i] = ((1LL * H1[i - 1] * 103) % MOD1 + 1LL * (s[i] - 'a')) % MOD1;
- // dbg(get_hash1(4, 6));
- int q;
- cin >> q;
- while (q--) {
- int l1, r1, l2, r2;
- cin >> l1 >> r1 >> l2 >> r2; l1--; l2--; r1--; r2--;
- substr lhs(l1, r1 - l1 + 1), rhs(l2, r2 - l2 + 1);
- if (lhs > rhs) {
- cout << ">" << endl;
- } else if (rhs > lhs) {
- cout << "<" << endl;
- } else {
- cout << "=" << endl;
- }
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- cout.precision(30);
- int t = 1;
- while (t--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement