Submission #1263761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263761		kustov_vadim_533	Modern Machine (JOI23_ho_t5)	C++20	0 / 100	0 ms	328 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;


struct obj{
	int sum = 0;
	char add = 'N';

	obj() = default;
	obj(char x) : sum(x == 'R') {};
};

const int sz = 1 << 20;
obj tree[sz];

void push(int v, int ln){
	if (tree[v].add == 'N') return;
	if (ln > 1){
		tree[v * 2].add = tree[v].add;
		tree[v * 2 + 1].add = tree[v].add;
	}
	tree[v].sum = (int)(tree[v].add == 'R') * ln;
	tree[v].add = 'N';
}

void upd(int v, int l, int r, int ql, int qr, char qx){
	push(v, r - l);
	if (l >= qr || ql >= r) return;
	if (l >= ql && r <= qr){
		tree[v].add = qx;
		push(v, r - l);
		return;
	}
	int m = (l + r) / 2;
	upd(v * 2, l, m, ql, qr, qx);
	upd(v * 2 + 1, m, r, ql, qr, qx);
	tree[v].sum = tree[v * 2].sum + tree[v * 2 + 1].sum;
}

int sum(int v, int l, int r, int ql, int qr){
	push(v, r - l);
	if (l >= qr || ql >= r) return 0;
	if (l >= ql && r <= qr) return tree[v].sum;
	int m = (l + r) / 2;
	int r1 = sum(v * 2, l, m, ql, qr);
	int r2 = sum(v * 2 + 1, m, r, ql, qr);
	return r1 + r2;
}

int find1(int v, int l, int r, int k){
	push(v, r - l);
	if (r - l == 1){
		if (k > tree[v].sum) return r;
		return l;
	}
	int m = (l + r) / 2;
	push(v * 2, m - l);
	if (tree[v * 2].sum >= k) return find1(v * 2, l, m, k);
	else return find1(v * 2 + 1, m, r, k - tree[v * 2].sum);
}

int find0(int v, int l, int r, int k){
	push(v, r - l);
	if (r - l == 1){
		if (k > r - l - tree[v].sum) return r;
		return l;
	}
	int m = (l + r) / 2;
	push(v * 2, m - l);
	if (m - l - tree[v * 2].sum >= k) return find0(v * 2, l, m, k);
	else return find0(v * 2 + 1, m, r, k - (m - l - tree[v * 2].sum));
}

void build(int v, int l, int r, vector<char>& a){
	tree[v].add = 'N';
	if (r - l == 1){
		tree[v] = obj(a[l]);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m, a);
	build(v * 2 + 1, m, r, a);
	tree[v].sum = tree[v * 2].sum + tree[v * 2 + 1].sum;
}

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];
	}

	int q;
	cin >> q;
	for (int j = 0; j < q; ++j){
		int l, r;
		cin >> l >> r;
		--l, --r;
		
		build(1, 0, n, c);

		for (int f = l; f <= r; ++f){
			upd(1, 0, n, a[f], a[f] + 1, 'R');

			int v = a[f];

			int k, u;

			while (v >= 0 && v < n){
				k = sum(1, 0, n, 0, v + 1);

				if (sum(1, 0, n, v, v + 1) == 0){
					u = -1;
					if (k > 0){
						u = find1(1, 0, n, k);
					}

					if (u >= 0){
						int li = -1;
						if (u + 1 - k > 0){
							li = find0(1, 0, n, u + 1 - k);
						}
						int ri = find1(1, 0, n, k + 1);

						int mn = min(u - li, ri - v);

						if (mn > 0){
							upd(1, 0, n, u - mn, u, 'B');
							v = v + mn;
							continue;
						}
					}

					upd(1, 0, n, u + 1, v + 1, 'R');
					v = u;
				}
				else{
					u = find0(1, 0, n, v + 2 - k);

					if (u < n){
						int li = -1;
						if (v + 1 - k > 0){
							li = find0(1, 0, n, v + 1 - k);
						}
						int ri = find1(1, 0, n, k + u - v);

						int mn = min(v - li, ri - u);
						if (mn > 0){
							upd(1, 0, n, u, u + mn, 'R');
							v = v - mn;
							continue;
						}
					}

					upd(1, 0, n, v, u, 'B');
					v = u;
				}
			}
		}
		cout << sum(1, 0, n, 0, n) << '\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: 0 / 11
• Subtask 5: 0 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21