oj.uz

Submission #525769

# Submission time Handle Problem Language Result Execution time Memory
525769 2022-02-12T20:03:02 Z sidon Collider (IZhO11_collider) C++17
100 / 100
 250 ms 2016 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))

#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.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 15 ms 972 KB Output is correct
4 Correct 73 ms 1888 KB Output is correct
5 Correct 140 ms 1864 KB Output is correct
6 Correct 186 ms 1888 KB Output is correct
7 Correct 198 ms 1896 KB Output is correct
8 Correct 88 ms 1896 KB Output is correct
9 Correct 250 ms 1904 KB Output is correct
10 Correct 175 ms 2016 KB Output is correct