Submission #916389

#	Time	Username	Problem	Language	Result	Execution time	Memory
916389		EJIC_B_KEDAX	Modern Machine (JOI23_ho_t5)	C++17	25 / 100	3052 ms	4692 KiB

Main

#include <bits/stdc++.h>

#define x first
#define y second

using ll = long long;

using namespace std;

const int N = 1 << 17, M = 120120;
int st[2 * N], lazy[2 * N], a[N], b[M];

void build() {
	for (int i = N - 1; i < 2 * N - 1; i++) {
		st[i] = a[i - N + 1];
		lazy[i] = -1;
	}
	for (int i = N - 2; i >= 0; i--) {
		st[i] = st[2 * i + 1] + st[2 * i + 2];
		lazy[i] = -1;
	}
}

void update_seg(int l, int r, int v, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		st[i] = v * (r1 - l1 + 1);
		lazy[i] = v;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	if (lazy[i] != -1) {
		st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
		st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
		lazy[2 * i + 1] = lazy[i];
		lazy[2 * i + 2] = lazy[i];
		lazy[i] = -1;
	}
	update_seg(l, r, v, l1, (l1 + r1) / 2, 2 * i + 1);
	update_seg(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	st[i] = st[2 * i + 1] + st[2 * i + 2];
}

int get_sum(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		return st[i];
	}
	if (l1 > r || r1 < l) {
		return 0;
	}
	if (lazy[i] != -1) {
		st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
		st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
		lazy[2 * i + 1] = lazy[i];
		lazy[2 * i + 2] = lazy[i];
		lazy[i] = -1;
	}
	return get_sum(l, r, l1, (l1 + r1) / 2, 2 * i + 1) + get_sum(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
}

int down_l(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 > r || r1 < l) {
		return -1;
	}
	if (s > st[i] || s < 0) {
		return -1;
	}
	if (l1 == r1 && s == st[i] && l1 >= l && r1 <= r) {
		return l1;
	} else if (l1 == r1) {
		return -1;
	}
	if (lazy[i] != -1) {
		st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
		st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
		lazy[2 * i + 1] = lazy[i];
		lazy[2 * i + 2] = lazy[i];
		lazy[i] = -1;
	}
	int v = get_sum(max(l, (l1 + r1) / 2 + 1), min(r, r1));
	int left = down_l(l, r, s - v, l1, (l1 + r1) / 2, 2 * i + 1);
	if (left == -1) {
		return down_l(l, r, s, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	}
	return left;
}

int down_r(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 > r || r1 < l) {
		return -1;
	}
	if (s > r1 - l1 + 1 - st[i] || s < 0) {
		return -1;
	}
	if (l1 == r1 && s == 1 - st[i] && l1 >= l && r1 <= r) {
		return l1;
	} else if (l1 == r1) {
		return -1;
	}
	if (lazy[i] != -1) {
		st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
		st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
		lazy[2 * i + 1] = lazy[i];
		lazy[2 * i + 2] = lazy[i];
		lazy[i] = -1;
	}
	int v = max(min(r, (l1 + r1) / 2) - max(l, l1) + 1 - get_sum(max(l, l1), min(r, (l1 + r1) / 2)), 0);
	int right = down_r(l, r, s - v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	if (right == -1) {
		return down_r(l, r, s, l1, (l1 + r1) / 2, 2 * i + 1);
	}
	return right;
}

int32_t main() {
	int n, m;
	cin >> n >> m;
	string as;
	cin >> as;
	for (int i = 0; i < n; i++) {
		a[i] = as[i] == 'B' ? 0 : 1;
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i]; b[i]--;
	}
	// cout << "!!\n";
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r; l--; r--;
		build();
		// cout << "!\n";
		for (int i = l; i <= r; i++) {
			int sl = get_sum(0, b[i] - 1), sr = n - b[i] - 1 - get_sum(b[i] + 1, n - 1);
			// cout << sl << ' ' << sr << '\n';
			if (sl < sr) {
				int gr = down_r(b[i] + 1, n - 1, sl + 1);
				// cout << "! " << gr << '\n';
				update_seg(0, gr, 1);
			} else {
				int gr = down_l(0, b[i] - 1, sr);
				// cout << "! " << gr << '\n';
				if (gr == -1) {
					gr = b[i];
				}
				update_seg(gr, n - 1, 0);
			}
		}
		cout << st[0] << '\n';
	}
}

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