Submission #1273383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273383		kaiboy	Rope (JOI17_rope)	C++20	100 / 100	821 ms	78296 KiB

rope

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int  N = 1000000;
const int N_ = 1 << 20;

int aa[N], st[N_ << 1], n_, ans[N];
vector<int> ii[N];

void pul(int i) {
	int l = i << 1, r = l ^ 1;
	st[i] = min(st[l], st[r]);
}

void build(int n) {
	for (n_ = 1; n_ < n; n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		st[i + n_] = 0;
	for (int i = n_ - 1; i; i--)
		pul(i);
}

void update(int i, int a) {
	st[i += n_] += a;
	while (i >>= 1)
		pul(i);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, a_; cin >> n >> a_;
	for (int i = 0; i < n; i++)
		cin >> aa[i], aa[i]--;
	for (int a = 0; a < a_; a++)
		ans[a] = n;
	for (int i_ = 0; i_ < 2; i_++) {
		build(a_);
		for (int a = 0; a < a_; a++)
			ii[a].clear();
		int s = 0;
		for (int i = i_; i <= n; i += 2) {
			if (i < n) {
				int a = aa[i];
				s++, update(a, -1);
				ii[a].push_back(i);
			}
			if (i) {
				int a = aa[i - 1];
				s++, update(a, -1);
				if (i == n || a != aa[i])
					ii[a].push_back(i);
			}
		}
		for (int a = 0; a < a_; a++) {
			int x = 0;
			for (int i : ii[a]) {
				if (i && i < n && aa[i] != aa[i - 1])
					x++;
				if (i < n) {
					int a = aa[i];
					s--, update(a, 1);
				}
				if (i) {
					int a = aa[i - 1];
					s--, update(a, 1);
				}
			}
			ans[a] = min(ans[a], x + s + st[1]);
			for (int i : ii[a]) {
				if (i < n) {
					int a = aa[i];
					s++, update(a, -1);
				}
				if (i) {
					int a = aa[i - 1];
					s++, update(a, -1);
				}
			}
		}
	}
	for (int a = 0; a < a_; a++)
		cout << ans[a] << '\n';
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20