Submission #916418

#	Time	Username	Problem	Language	Result	Execution time	Memory
916418		EJIC_B_KEDAX	Modern Machine (JOI23_ho_t5)	C++17	36 / 100	3062 ms	18272 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 = 1 << 17, A = 11;
int st[2 * N], lazy[2 * N], a[N], b[M], st1[3 * M][A], fre = 3 * M - 2;

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

void merge(int to, int a, int b) {
	for (int i = 0; i < A; i++) {
		st1[to][i] = st1[b][st1[a][i]];
	}
}

int get_ans(int l, int r, int l1 = 0, int r1 = M - 1, int i = 0) {
	if (l1 > r || r1 < l) {
		return 3 * M - 1;
	}
	if (l1 >= l && r1 <= r) {
		for (int j = 0; j < A; j++) {
			st1[fre][j] = st1[i][j];
		}
		return fre--;
	}
	int ans = fre--;
	merge(ans, get_ans(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_ans(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
	return ans;
}

int32_t main() {
	int n, m;
	for (int i = 0; i < A; i++) {
		st1[3 * M - 1][i] = i;
	}
	cin >> n >> m;
	int sum = 0;
	string as;
	cin >> as;
	for (int i = 0; i < n; i++) {
		a[i] = as[i] == 'B' ? 0 : 1;
		sum += a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i]; b[i]--;
	}
	// cout << "!!\n";
	int q;
	cin >> q;
	if (n != 10 || sum != 10) {
		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';
		}
	} else {
		int pr[A][A];
		build();
		for (int i = 0; i < n; i++) {
			update_seg(0, n - 1, 0);
			for (int j = 0; j < A; j++) {
				update_seg(0, j - 1, 1);
				int sl = get_sum(0, i - 1), sr = n - i - 1 - get_sum(i + 1, n - 1);
				if (sl < sr) {
					int gr = down_r(i + 1, n - 1, sl + 1);
					pr[i][j] = max(gr + 1, j);
				} else {
					int gr = down_l(0, i - 1, sr);
					if (gr == -1) {
						gr = i;
					}
					pr[i][j] = min(gr, j);
				}
				// cout << pr[i][j] << ' ';
			}
			// cout << '\n';
		}
		for (int i = M - 1; i < 2 * M - 1; i++) {
			if (i - M + 1 < m) {
				for (int j = 0; j < A; j++) {
					st1[i][j] = pr[b[i - M + 1]][j];
				}
			} else {
				for (int j = 0; j < A; j++) {
					st1[i][j] = j;
				}
			}
		}
		for (int i = M - 2; i >= 0; i--) {
			merge(i, 2 * i + 1, 2 * i + 2);
		}
		while (q--) {
			int l, r;
			cin >> l >> r; l--; r--;
			fre = 3 * M - 2;
			cout << st1[get_ans(l, r)][10] << '\n';
		}
	}
}

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