제출 #1263642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263642		kustov_vadim_533	Modern Machine (JOI23_ho_t5)	C++20	3 / 100	3095 ms	836 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 cnt0 = 0, cnt1 = 0;
	char add = 'N';

	obj() = default;
	obj(int x) : cnt0(x == 'B'), cnt1(x == 'R') {};
};

obj merge(obj &a, obj &b){
	obj res;
	res.cnt0 = a.cnt0 + b.cnt0;
	res.cnt1 = a.cnt1 + b.cnt1;
	return res;
}

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].cnt0 = (tree[v].add == 'B') * ln;
	tree[v].cnt1 = (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] = merge(tree[v * 2], tree[v * 2 + 1]);
}

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

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

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

void build(int v, int l, int r, vector<char>& a){
	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] = merge(tree[v * 2], tree[v * 2 + 1]);
}

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

			while (v >= 0 && v < n){
				if (sum(1, 0, n, v, v + 1).cnt0 == 1){
					int k = sum(1, 0, n, 0, v + 1).cnt1;
					int u = -1;
					if (k > 0){
						u = find1(1, 0, n, k);
					}

					upd(1, 0, n, u + 1, v + 1, 'R');
					v = u;
				}
				else{
					int k = sum(1, 0, n, 0, v + 1).cnt0;
					int u = find0(1, 0, n, k + 1);

					upd(1, 0, n, v, u, 'B');
					v = u;
				}
			}
		}
		cout << sum(1, 0, n, 0, n).cnt1 << '\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: 3 / 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