Submission #525686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525686	2022-02-12T14:34:10 Z	sidon	Collider (IZhO11_collider)	C++17	0 / 100	17 ms	716 KB

collider

#include <bits/stdc++.h>
using namespace std;
#define i64 int64_t

const int Z = 1e6+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[3];

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)
		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, 2})
					a[i].shiftToL(l, r);
			else
				for(int i : {0, 1, 2})
					a[i].shiftToR(r-1, l+1);

		} else
			cout << char('x' + (a[1][l]) + (2*a[2][l])) << '\n';
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	708 KB	Output is correct
2	Incorrect	17 ms	716 KB	Output isn't correct
3	Halted	0 ms	0 KB	-