Submission #525769

#	Time	Username	Problem	Language	Result	Execution time	Memory
525769		sidon	Collider (IZhO11_collider)	C++17	100 / 100	250 ms	2016 KiB

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 = 1<<7;

#define mask(I) (num(1)<<(I))
#define setBit(X, I, V) (X ^= (allOn[V] ^ X) & mask(I))

#define blk(X) ((X)>>7)
#define pos(X) ((X)&(B-1))

	num v[blk(n)+1] = {}, allOn[2] = {0, -1};
	BitSet() {}

	inline bool operator[](int i) {
		return v[blk(i)] & mask(pos(i));
	}
	void assign(int i, bool val) {
		setBit(v[blk(i)], pos(i), val);
	}
	void shiftToR(int l, int r) { // [l, r)
		bool prev = (*this)[r-1], nPrev;
 
		for(int i = l; i < r; ) {
			if(!pos(i) && i + B <= r) {
				nPrev = v[blk(i)] & mask(B - 1);
				v[blk(i)] <<= 1;
				setBit(v[blk(i)], 0, prev);
				prev = nPrev;
				i += B;
			} else {
				num x = v[blk(i)];
				int j = min(r, (blk(i) + 1) * B);
 
				for(; i < j; ++i) {
					setBit(v[blk(i)], pos(i), prev);
					prev = bool(x & mask(pos(i)));
				}
			}
		}
	}
	void shiftToL(int l, int r) { // [l, r)
		bool prev = (*this)[l], nPrev;
 
		for(int i = l; i < r; ) {
			if(!pos(i) && i + B <= r) {
				nPrev = (i + B == r ? prev : (*this)[i+B]);

				v[blk(i)] >>= 1;
				setBit(v[blk(i)], B-1, nPrev);
				i += B;
			} else {
				int j = min(r, (blk(i) + 1) * B);
 
				for(; i < j; ++i) {
					nPrev = i+1 == r ? prev : (*this)[i+1];
					setBit(v[blk(i)], pos(i), 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 / 100