# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
525751 | sidon | Collider (IZhO11_collider) | C++17 | 12 ms | 716 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 128;
num v[n/B+1] = {}, bit[B], _bit[B] = {};
BitSet() {
bit[0] = 1;
for(int i = 1; i < B; ++i)
bit[i] = bit[i-1] + bit[i-1];
for(int i = 0; i < B; ++i)
for(int j = 0; j < B; ++j)
if(i != j) _bit[i] |= bit[j];
}
inline bool operator[](int i) {
return v[i / B] & bit[i % B];
}
void assign(int i, bool val) {
if(val)
v[i / B] |= bit[i % B];
else
v[i / B] &= _bit[i % B];
}
void shiftToR(int l, int r) { // [l, r)
bool prev = (*this)[r-1], nPrev;
for(int i = l; i < r; ) {
num &y = v[i/B];
if(!(i % B) && i + B <= r) {
nPrev = y & bit[B-1];
y = ((y & _bit[B-1]) << 1) | num(prev);
prev = nPrev;
i += B;
} else {
num x = v[i/B];
int j = min(r, (i/B + 1) * B);
int k = i % B;
for(int c = i; c < j; ++c, ++k) {
y = prev ? (bit[k] | y) : (_bit[k] & y);
prev = bool(x & bit[k]);
}
i = j;
}
}
}
void shiftToL(int l, int r) { // [l, r)
bool prev = (*this)[l], nPrev;
for(int i = l; i < r; ) {
num &y = v[i/B];
if(!(i % B) && i + B <= r) {
nPrev = (i + B == r ? prev : (*this)[i+B]);
y = (y >> 1) | (nPrev ? bit[B-1] : num(0));
i += B;
} else {
int j = min(r, (i/B + 1) * B);
int k = i % B;
for(int c = i; c < j; ++c, ++k) {
nPrev = c+1 == r ? prev : (*this)[c+1];
y = nPrev ? (bit[k] | y) : (_bit[k] & y);
}
i = j;
}
}
}
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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |