oj.uz

Submission #525767

# Submission time Handle Problem Language Result Execution time Memory
525767 2022-02-12T19:57:30 Z sidon Collider (IZhO11_collider) C++17
100 / 100
 282 ms 1896 KB 
#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; ) {
			num &y = v[i/B];
 
			if(!(i % B) && i + B <= r) {
				nPrev = y & mask(B - 1);
				y <<= 1;
				setBit(y, 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(y, 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; ) {
			num &y = v[i/B];
 
			if(!(i % B) && i + B <= r) {
				nPrev = (i + B == r ? prev : (*this)[i+B]);

				y >>= 1;
				setBit(y, 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(y, 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';
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 12 ms 716 KB Output is correct
3 Correct 16 ms 1016 KB Output is correct
4 Correct 87 ms 1888 KB Output is correct
5 Correct 159 ms 1888 KB Output is correct
6 Correct 212 ms 1888 KB Output is correct
7 Correct 228 ms 1896 KB Output is correct
8 Correct 102 ms 1896 KB Output is correct
9 Correct 282 ms 1896 KB Output is correct
10 Correct 189 ms 1896 KB Output is correct