Submission #525766

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525766	2022-02-12T19:52:02 Z	sidon	Collider (IZhO11_collider)	C++17	100 / 100	327 ms	1896 KB

collider

#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;

#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, ~num(0)};
	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);
				setBit(y, B-1, 0);
				y <<= 1;
				setBit(y, 0, 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) {
					setBit(y, k, prev);
					prev = bool(x & mask(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 >>= 1;
				setBit(y, B-1, nPrev);
				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];
					setBit(y, k, nPrev);
				}
				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';
		}
	}
}

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	20 ms	972 KB	Output is correct
4	Correct	94 ms	1888 KB	Output is correct
5	Correct	175 ms	1888 KB	Output is correct
6	Correct	231 ms	1888 KB	Output is correct
7	Correct	265 ms	1896 KB	Output is correct
8	Correct	113 ms	1896 KB	Output is correct
9	Correct	327 ms	1896 KB	Output is correct
10	Correct	230 ms	1896 KB	Output is correct