Advertisement
he_obviously

Untitled

Jan 2nd, 2021
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize("unroll-loops")
  3. //#pragma GCC target("sse,sse2,ssse3,sse3,sse4,avx,avx2,popcnt,tune=native")
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <string>
  8. #include <queue>
  9. #include <set>
  10. #include <iomanip>
  11. #include <map>
  12. #include <algorithm>
  13. #include <cmath>
  14. #include <bitset>
  15. #include <limits.h>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21.  
  22. #define all(x) (x).begin(),(x).end()
  23. #define pii pair<int, int>
  24. #define sz(x) (int)x.size()
  25.  
  26. const ll o = 31, MOD1 = 1000 * 1000 * 1000 + 33, MOD2 = 1000 * 1000 * 1000 + 9;
  27.  
  28. int main() {
  29.  
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0); cout.tie(0);
  32.  
  33.     string s;
  34.     cin >> s;
  35.  
  36.     int n = sz(s);
  37.  
  38.     vector<ll> pf(n + 1, 1), ps(n + 1, 1);
  39.     for (int i = 1; i <= n; ++i) {
  40.         pf[i] = (pf[i - 1] * o) % MOD1;
  41.         ps[i] = (ps[i - 1] * o) % MOD2;
  42.     }
  43.  
  44.     vector<ll> hf(n), hs(n);
  45.     hf[0] = (ll)(s[0] - 'a' + 1);
  46.     hs[0] = (ll)(s[0] - 'a' + 1);
  47.     for (int i = 1; i < n; ++i) {
  48.         hf[i] = (hf[i - 1] + (ll)(s[i] - 'a' + 1) * pf[i]) % MOD1;
  49.         hs[i] = (hs[i - 1] + (ll)(s[i] - 'a' + 1) * ps[i]) % MOD2;
  50.     }
  51.  
  52.     int k;
  53.     cin >> k;
  54.  
  55.     for (int i = 0; i < k; ++i) {
  56.         int l1, r1, l2, r2;
  57.         cin >> l1 >> r1 >> l2 >> r2;
  58.         --l1; --r1; --l2; --r2;
  59.         if (r1 - l1 != r2 - l2) {
  60.             cout << "No\n";
  61.         }
  62.         else {
  63.             ll h1 = (hf[r1] - (l1 == 0 ? 0 : hf[l1 - 1]) + MOD1) % MOD1,
  64.                 h2 = (hf[r2] - (l2 == 0 ? 0 : hf[l2 - 1]) + MOD1) % MOD1;
  65.             h1 = (h1 * (l2 <= l1 ? 1 : pf[l2 - l1])) % MOD1;
  66.             h2 = (h2 * (l1 <= l2 ? 1 : pf[l1 - l2])) % MOD1;
  67.             ll h3 = (hs[r1] - (l1 == 0 ? 0 : hs[l1 - 1]) + MOD2) % MOD2,
  68.                 h4 = (hs[r2] - (l2 == 0 ? 0 : hs[l2 - 1]) + MOD2) % MOD2;
  69.             h3 = (h3 * (l2 <= l1 ? 1 : ps[l2 - l1])) % MOD2;
  70.             h4 = (h4 * (l1 <= l2 ? 1 : ps[l1 - l2])) % MOD2;
  71.             cout << (h1 == h2 && h3 == h4 ? "Yes\n" : "No\n");
  72.         }
  73.     }
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement