제출 #1263810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263810		kustov_vadim_533	Modern Machine (JOI23_ho_t5)	C++20	11 / 100	1317 ms	2200 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
	for  (auto& x : a){
		out << x << ' ';
	}
	out << '\n';
	return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T> &a){
	for (size_t i = 0; i < a.size(); ++i){
		in >> a[i];
	}
	return in;
}


mt19937 gen;

const int N = 10;
const int M = 125000;
const int B = 500;

int bl[M / B][1 << N];
int l[M / B], r[M / B];

int tr[N][1 << N];
int sz[1 << N];

inline void solve() {
	int n, m;
	cin >> n >> m;
	vector<char> c(n);
	vector<int> a(m);
	for (int i = 0; i < n; ++i){
		cin >> c[i];
	}
	for (int j = 0; j < m; ++j){
		cin >> a[j];
		--a[j];
	}

	for (int i = 0; i < (1 << n); ++i){
		sz[i] = 0;
		for (int j = 0; j < n; ++j){
			sz[i] += (i >> j) & 1;
		}
		for (int f = 0; f < n; ++f){
			vector<char> b(n);
			for (int j = 0; j < n; ++j){
				if ((i >> j) & 1){
					b[j] = 'R';
				}
				else{
					b[j] = 'B';
				}
			}

			b[f] = 'R';
			int v = f;
			while (v >= 0 && v < n){
				if (b[v] == 'R'){
					b[v] = 'B';
					++v;
				}
				else{
					b[v] = 'R';
					--v;
				}
			}

			int w = 0;			
			for (int j = 0; j < n; ++j){
				w |= ((int)(b[j] == 'R') << j);
			}
			tr[f][i] = w;
		}
	}

	for (int i = 0; i < M / B; ++i){
		for (int j = 0; j < (1 << N); ++j){
			bl[i][j] = j;
		}
	}

	l[0] = 0;
	for (int i = 0; i < m; ++i){
		r[i / B] = i;
		l[i / B + 1] = i + 1;
	}

	for (int i = 0; i < m; ++i){
		for (int j = 0; j < (1 << N); ++j){
			bl[i / B][j] = tr[a[i]][bl[i / B][j]];
		}
	}


	int st = 0;
	for (int j = 0; j < n; ++j){
		st |= ((int)(c[j] == 'R') << j);
	}

	int q;
	cin >> q;
	for (int j = 0; j < q; ++j){
		int li, ri;
		cin >> li >> ri;
		--li, --ri;

		int v = st;

		for (int bf = li / B; bf <= ri / B; ++bf){
			if (l[bf] >= li && r[bf] <= ri){
				v = bl[bf][v];
			}
			else{
				for (int f = max(li, l[bf]); f <= min(ri, r[bf]); ++f){
					v = tr[a[f]][v];
				}
			}
		}

		cout << sz[v] << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 12
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21