fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double
  5. #define all(v) v.begin(), v.end()
  6. #define rall(v) v.rbegin(), v.rend()
  7. #define f(i, a, n) for (int i = (a); i <= (n); i++)
  8. #define ff first
  9. #define ss second
  10. #define UWU ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  11. void __print(int x) { cerr << x; }
  12. void __print(long x) { cerr << x; }
  13. void __print(long long x) { cerr << x; }
  14. void __print(unsigned x) { cerr << x; }
  15. void __print(unsigned long x) { cerr << x; }
  16. void __print(unsigned long long x) { cerr << x; }
  17. void __print(float x) { cerr << x; }
  18. void __print(double x) { cerr << x; }
  19. void __print(long double x) { cerr << x; }
  20. void __print(char x) { cerr << '\'' << x << '\''; }
  21. void __print(const char *x) { cerr << '\"' << x << '\"'; }
  22. void __print(const string &x) { cerr << '\"' << x << '\"'; }
  23. void __print(bool x) { cerr << (x ? "true" : "false"); }
  24.  
  25. template <typename T, typename V>
  26. void __print(const pair<T, V> &x)
  27. {
  28.     cerr << '{';
  29.     __print(x.first);
  30.     cerr << ',';
  31.     __print(x.second);
  32.     cerr << '}';
  33. }
  34. template <typename T>
  35. void __print(const T &x)
  36. {
  37.     int f = 0;
  38.     cerr << '{';
  39.     for (auto &i : x)
  40.         cerr << (f++ ? "," : ""), __print(i);
  41.     cerr << "}";
  42. }
  43. void _print() { cerr << "]\n"; }
  44. template <typename T, typename... V>
  45. void _print(T t, V... v)
  46. {
  47.     __print(t);
  48.     if (sizeof...(v))
  49.         cerr << ", ";
  50.     _print(v...);
  51. }
  52. #ifndef ONLINE_JUDGE
  53. #define debug(x...)               \
  54.     cerr << "[" << #x << "] = ["; \
  55.     _print(x)
  56. #else
  57. #define debug(x...)
  58. #endif
  59.  
  60. const ll N = 1e5 + 5, mod = 998244353, p1 = 31, mod2 = 1e9 + 9, p2 = 37, M = 9e6 + 5;
  61.  
  62. void solve()
  63. {
  64.     ll n, q;
  65.     cin >> n >> q;
  66.     vector<ll> a(n);
  67.     char c;
  68.     ll len = sqrt(n) + 1;
  69.     vector<vector<ll>> b(len);
  70.     for (ll i = 0; i < n; i++)
  71.     {
  72.         cin >> c;
  73.         a[i] = c - 'a';
  74.         b[i / len].push_back(a[i]);
  75.     }
  76.     vector<ll> lazy(len, 0), valid(len, 0);
  77.     auto updateLazy = [&](ll i)
  78.     {
  79.         for (ll j = 0; j < b[i].size(); j++)
  80.         {
  81.             b[i][j] += lazy[i];
  82.             b[i][j] %= 26;
  83.         }
  84.         lazy[i] = 0;
  85.     };
  86.     auto updateValidity = [&](ll i)
  87.     {
  88.         updateLazy(i);
  89.         if (b[i].size() < 2)
  90.             return;
  91.         bool f = 0;
  92.         for (ll j = 1; j < b[i].size(); j++)
  93.         {
  94.             if (b[i][j] == b[i][j - 1])
  95.                 f = 1;
  96.             if (j > 1)
  97.                 if (b[i][j] == b[i][j - 2])
  98.                     f = 1;
  99.         }
  100.         valid[i] = f;
  101.     };
  102.  
  103.     auto updatePos = [&](ll i, ll block, ll x)
  104.     {
  105.         b[block][i] += x;
  106.         b[block][i] %= 26;
  107.     };
  108.     auto check = [&](ll b1, ll b2)
  109.     {
  110.         ll p1 = b1 / len;
  111.         ll p2 = b2 / len;
  112.         ll n1 = (b[p1][b1 % len] + lazy[p1]) % 26;
  113.         ll n2 = (b[p2][b2 % len] + lazy[p2]) % 26;
  114.         return (n1 == n2);
  115.     };
  116.     for (ll i = 0; i < len; i++)
  117.         updateValidity(i);
  118.     ll op, l, r, x;
  119.  
  120.     while (q--)
  121.     {
  122.         cin >> op >> l >> r;
  123.         l--, r--;
  124.         if (op == 1)
  125.         {
  126.             cin >> x;
  127.             for (ll i = l; i <= r;)
  128.             {
  129.                 ll block = i / len;
  130.                 if ((i % len == 0) && (i + len - 1 <= r))
  131.                 {
  132.                     lazy[block] += x;
  133.                     i += len;
  134.                 }
  135.                 else
  136.                 {
  137.                     updatePos(i % len, i / len, x);
  138.                     i++;
  139.                 }
  140.             }
  141.             updateValidity(l / len);
  142.             updateValidity(r / len);
  143.         }
  144.         else
  145.         {
  146.             bool t = 0;
  147.             for (ll i = l; i <= r;)
  148.             {
  149.                 ll block = i / len;
  150.                 if ((i % len == 0) && (i + len - 1 <= r))
  151.                 {
  152.                     if (valid[block])
  153.                         t |= 1;
  154.                     i += len;
  155.                 }
  156.                 else
  157.                 {
  158.                     i++;
  159.                 }
  160.             }
  161.             for (ll i = l; i <= r;)
  162.             {
  163.                 ll block = i / len;
  164.                 if ((i % len == 0) && (i + len - 1 <= r))
  165.                 {
  166.                     if (i + 1 <= r)
  167.                         t |= check(i, i + 1);
  168.                     if (i + 2 <= r)
  169.                         t |= check(i, i + 2);
  170.                     if (i - 1 >= l)
  171.                         t |= check(i, i - 1);
  172.                     if (i - 2 >= l)
  173.                         t |= check(i, i - 2);
  174.                     i += len;
  175.                 }
  176.                 else
  177.                 {
  178.                     if (i + 1 <= r)
  179.                         t |= check(i, i + 1);
  180.                     if (i + 2 <= r)
  181.                         t |= check(i, i + 2);
  182.                     if (i - 1 >= l)
  183.                         t |= check(i, i - 1);
  184.                     if (i - 2 >= l)
  185.                         t |= check(i, i - 2);
  186.                     i++;
  187.                 }
  188.             }
  189.             if (t)
  190.                 cout
  191.                     << "NO\n";
  192.             else
  193.                 cout << "YES\n";
  194.         }
  195.     }
  196. }
  197. int main()
  198. {
  199.     UWU;
  200.     int tc = 1;
  201.     cin >> tc;
  202.     cout << fixed << setprecision(30);
  203.     while (tc--)
  204.     {
  205.  
  206.         solve();
  207.     }
  208. }
  209. /*
  210.  
  211. */
Runtime error #stdin #stdout #stderr 0.01s 5348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/i2ZCpT
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!