Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1.  
  2.  
  3.  
  4. //#define FAST_ALLOCATOR_MEMORY 1e8
  5. #include "optimization.h"
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef unsigned long long ull;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef double dd;
  14. typedef vector<ll> vi;
  15. typedef vector<vector<ll>> vvi;
  16. typedef vector<ll> vll;
  17. typedef vector<vector<ll>> vvl;
  18. typedef vector<pair<ll, ll>> vpii;
  19. typedef pair<ll, ll> pii;
  20. typedef vector<pair<ll, ll>> vpll;
  21. typedef pair<ll, ll> pll;
  22.  
  23. #define mp make_pair
  24. #define pb push_back
  25. #define ff first
  26. #define ss second
  27. #define all(c) (c).begin(), (c).end()
  28. #define MOD 1000000007
  29. #define INF 999999999999999999
  30.  
  31. const int p = 29;
  32.  
  33. string s;
  34. vll power;
  35. vll arr;
  36.  
  37. ll precalc(){
  38.     int sz = s.size();
  39.     power[0] = 1;
  40.     for(ll i = 1; i < sz; i++) {
  41.         power[i] = (power[i - 1] * p) % MOD;
  42.     }
  43.  
  44.     for(int i = 0; i < sz; i++) {
  45.         arr[i] = (s[i] - 'a' + 1) * power[i];
  46.         arr[i] %= MOD;
  47.         if (i) {
  48.             arr[i] += arr[i - 1];
  49.             arr[i] %= MOD;
  50.         }
  51.     }
  52. }
  53.  
  54. int main() {
  55. #ifdef HOME
  56.     freopen("kek.in", "r", stdin);
  57.     freopen("kek.out", "w", stdout);
  58. #endif
  59.     char st[100000 + 5];
  60.     readWord(st);
  61.     s = string(st);
  62.     power.resize(s.size(), 0);
  63.     arr.resize(s.size(), 0);
  64.     power[0] = 1;
  65.     precalc();
  66.     int n, a, b, c, d;
  67.     n = readInt();
  68.     for(int i = 0; i < n; i++){
  69.         a = readInt() - 1;
  70.         b = readInt() - 1;
  71.         c = readInt() - 1;
  72.         d = readInt() - 1;
  73.  
  74.         if(b - a != d - c) {
  75.             writeWord("No\n");
  76.             continue;
  77.         }
  78.         if(a == c && b == d){
  79.             writeWord("Yes\n");
  80.             continue;
  81.         }
  82.         ll len = b - a + 1;
  83.         ll h1 = arr[a + len - 1];
  84.         if(a){
  85.             h1 = (h1 - arr[a - 1] + MOD) % MOD;
  86.         }
  87.  
  88.         ll h2 = arr[c + len - 1];
  89.         if(c){
  90.             h2 = (h2 - arr[c - 1] + MOD) % MOD;
  91.         }
  92.  
  93.         if((a < c && (h1 * power[c - a]) % MOD == h2) || (a > c && h1 == (h2 * power[a - c]) % MOD)) {
  94.             writeWord("Yes\n");
  95.         }
  96.         else {
  97.             writeWord("No\n");
  98.         }
  99.     }
  100.     // for(auto a : arr)
  101.     //     cout << a << " ";
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement