oj.uz

Submission #916416

# Submission time Handle Problem Language Result Execution time Memory
916416 2024-01-25T20:13:30 Z EJIC_B_KEDAX Modern Machine (JOI23_ho_t5) C++17
25 / 100
 1244 ms 16728 KB 
#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 - 1; 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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 10 ms 3928 KB Output is correct
11 Correct 6 ms 3676 KB Output is correct
12 Correct 13 ms 3832 KB Output is correct
13 Correct 13 ms 3828 KB Output is correct
14 Correct 14 ms 3672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 10 ms 3928 KB Output is correct
11 Correct 6 ms 3676 KB Output is correct
12 Correct 13 ms 3832 KB Output is correct
13 Correct 13 ms 3828 KB Output is correct
14 Correct 14 ms 3672 KB Output is correct
15 Correct 2 ms 3676 KB Output is correct
16 Correct 5 ms 16140 KB Output is correct
17 Correct 2 ms 3676 KB Output is correct
18 Correct 858 ms 4912 KB Output is correct
19 Correct 917 ms 4768 KB Output is correct
20 Correct 1185 ms 4860 KB Output is correct
21 Correct 1244 ms 4904 KB Output is correct
22 Correct 908 ms 4736 KB Output is correct
23 Correct 854 ms 4828 KB Output is correct
24 Correct 824 ms 4684 KB Output is correct
25 Correct 835 ms 4424 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16216 KB Output is correct
2 Correct 293 ms 16344 KB Output is correct
3 Correct 323 ms 16388 KB Output is correct
4 Incorrect 292 ms 16728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16216 KB Output is correct
2 Correct 293 ms 16344 KB Output is correct
3 Correct 323 ms 16388 KB Output is correct
4 Incorrect 292 ms 16728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16216 KB Output is correct
2 Correct 293 ms 16344 KB Output is correct
3 Correct 323 ms 16388 KB Output is correct
4 Incorrect 292 ms 16728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 10 ms 3928 KB Output is correct
11 Correct 6 ms 3676 KB Output is correct
12 Correct 13 ms 3832 KB Output is correct
13 Correct 13 ms 3828 KB Output is correct
14 Correct 14 ms 3672 KB Output is correct
15 Correct 2 ms 3676 KB Output is correct
16 Correct 5 ms 16140 KB Output is correct
17 Correct 2 ms 3676 KB Output is correct
18 Correct 858 ms 4912 KB Output is correct
19 Correct 917 ms 4768 KB Output is correct
20 Correct 1185 ms 4860 KB Output is correct
21 Correct 1244 ms 4904 KB Output is correct
22 Correct 908 ms 4736 KB Output is correct
23 Correct 854 ms 4828 KB Output is correct
24 Correct 824 ms 4684 KB Output is correct
25 Correct 835 ms 4424 KB Output is correct
26 Correct 5 ms 16216 KB Output is correct
27 Correct 293 ms 16344 KB Output is correct
28 Correct 323 ms 16388 KB Output is correct
29 Incorrect 292 ms 16728 KB Output isn't correct
30 Halted 0 ms 0 KB -