Submission #203232

#	Time	Username	Problem	Language	Result	Execution time	Memory
203232		Noam527	Rope (JOI17_rope)	C++17	100 / 100	1174 ms	76920 KiB

rope

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

const int N = 1e6 + 10;

int n, m, a[N];
vector<int> pos[N];

int mx;
int freq[N] = {};
int freq_count[N] = {};

void add(int val) {
	if (OO) cout << "adding " << val << '\n';
	--freq_count[freq[val]];
	++freq[val];
	++freq_count[freq[val]];
	mx = max(mx, freq[val]);
}
void del(int val) {
	if (OO) cout << "deleting " << val << '\n';
	--freq_count[freq[val]];
	if (mx == freq[val] && !freq_count[freq[val]])
		--mx;
	--freq[val];
	++freq_count[freq[val]];
}
int query() {
	if (OO) cout << "query: " << mx << '\n';
	return mx;
}
void prep() {
	freq_count[0] = n;
	mx = 0;
	for (int i = 0; i < n; i++)
		add(a[i]);
}

int solve(int v) {
	if (OO) cout << "started solve(" << v << "):\n";
	vector<int> even, odd;
	for (const auto &i : pos[v]) {
		int e = (i & 1) ? i - 1 : i;
		int o = (i & 1) ? i : i - 1;
		if (!even.size() || even.back() != e) even.push_back(e);
		if (o > 0 && (!odd.size() || odd.back() != o)) odd.push_back(o);
	}

	int start, remain, mn = md;

	// try even
	start = 0;
	remain = n;
	for (const auto &i : even) {
		del(a[i]);
		remain--;
		if (a[i] != v)
			start++;
		if (i + 1 < n) {
			del(a[i + 1]);
			remain--;
			if (a[i + 1] != v)
				start++;
		}
	}
	mn = min(mn, start + remain - query());
	for (const auto &i : even) {
		add(a[i]);
		if (i + 1 < n)
			add(a[i + 1]);
	}
	// try odd
	start = 0;
	remain = n;
	if (a[0] == v) {
		del(a[0]);
		remain--;
	}
	for (const auto &i : odd) {
		del(a[i]);
		remain--;
		if (a[i] != v)
			start++;
		if (i + 1 < n) {
			del(a[i + 1]);
			remain--;
			if (a[i + 1] != v)
				start++;
		}
	}
	mn = min(mn, start + remain - query());
	if (a[0] == v)
		add(a[0]);
	for (const auto &i : odd) {
		add(a[i]);
		if (i + 1 < n)
			add(a[i + 1]);
	}

	return mn;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		--a[i];
		pos[a[i]].push_back(i);
	}
	prep();
	for (int i = 0; i < m; i++)
		cout << solve(i) << '\n';
}

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