Submission #525768

#TimeUsernameProblemLanguageResultExecution timeMemory
525768sidonCollider (IZhO11_collider)C++17
100 / 100
294 ms1900 KiB
#include <bits/stdc++.h> using namespace std; #define i64 int64_t const int Z = 2e6+1; template<const int n> struct BitSet { using num = __int128; static const int B = 1<<7; #define mask(I) (num(1)<<(I)) #define setBit(X, I, V) (X ^= (allOn[V] ^ X) & mask(I)) num v[n/B+1] = {}, allOn[2] = {0, -1}; BitSet() {} inline bool operator[](int i) { return v[i / B] & mask(i % B); } void assign(int i, bool val) { setBit(v[i/B], i%B, val); } void shiftToR(int l, int r) { // [l, r) bool prev = (*this)[r-1], nPrev; for(int i = l; i < r; ) { if(!(i % B) && i + B <= r) { nPrev = v[i/B] & mask(B - 1); v[i/B] <<= 1; setBit(v[i/B], 0, prev); prev = nPrev; i += B; } else { num x = v[i/B]; int j = min(r, (i/B + 1) * B); for(; i < j; ++i) { setBit(v[i/B], i % B, prev); prev = bool(x & mask(i % B)); } } } } void shiftToL(int l, int r) { // [l, r) bool prev = (*this)[l], nPrev; for(int i = l; i < r; ) { if(!(i % B) && i + B <= r) { nPrev = (i + B == r ? prev : (*this)[i+B]); v[i/B] >>= 1; setBit(v[i/B], B-1, nPrev); i += B; } else { int j = min(r, (i/B + 1) * B); for(; i < j; ++i) { nPrev = i+1 == r ? prev : (*this)[i+1]; setBit(v[i/B], i % B, nPrev); } } } } operator unsigned long long() { return v[0]; } }; BitSet<Z> a[2]; int N, M; string s; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> N >> M >> s; for(int i = 0; i < N; ++i) if(s[i] != 'z') a[s[i] - 'x'].assign(i, 1); char t; int l, r; while(M--) { cin >> t >> l; --l; if(t == 'a') { cin >> r; if(l < r) for(int i : {0, 1}) a[i].shiftToL(l, r); else for(int i : {0, 1}) a[i].shiftToR(r-1, l+1); } else { char c = 'z'; if(a[0][l]) c = 'x'; if(a[1][l]) c = 'y'; cout << c << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...