Submission #684673

#	Time	Username	Problem	Language	Result	Execution time	Memory
684673		ethening	Rope (JOI17_rope)	C++17	100 / 100	1053 ms	84428 KiB

rope

#include "bits/stdc++.h"
#include <utility>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 1000000;
const int MAXM = 1000000;

int n, m;
int a[MAXN + 5];

vector<int> v[MAXM + 5];
int pairing[MAXN + 5];

int ans[MAXM + 5];

int cnt[MAXM + 5];
int cntOcc[MAXN + 5];

int mx;

void del(int x) {
	--cntOcc[cnt[x]];
	if (cntOcc[cnt[x]] == 0 && mx == cnt[x]) --mx;
	++cntOcc[--cnt[x]];
}

void ins(int x) {
	--cntOcc[cnt[x]];
	if (mx == cnt[x]) ++mx;
	++cntOcc[++cnt[x]];
}

void solve() {
	// for (int j = 1; j <= m; j++) {
	// 	cout << "@@" << j << " " << cnt[j] << endl;
	// }
	// for (int j = 1; j <= n; j++) {
	// 	cout << "!@# " << j << " " << cntOcc[j] << endl;
	// }
	// cout << "@@" << mx << endl;
	for (int i = 1; i <= m; i++) {
		int oricol = cnt[i];
		for (int j = 1; j <= oricol; j++) {
			del(i);
		}

		for (int x : v[i]) {
			if (pairing[x] != 0 && a[pairing[x]] != a[x]) {
				del(a[pairing[x]]);
			}
		}

		// for (int j = 1; j <= m; j++) {
		// 	cout << "##" << j << " " << cnt[j] << endl;
		// }

		ans[i] = min(ans[i], n - oricol - mx);
		// cout << "!!!" << i << " " << mx << " " << ans[i] << endl;

		for (int x : v[i]) {
			if (pairing[x] != 0 && a[pairing[x]] != a[x]) {
				ins(a[pairing[x]]);
			}
		}

		for (int j = 1; j <= oricol; j++) {
			ins(i);
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;

	if (m == 1) {
		cout << "0\n";
		return 0;
	}

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		v[a[i]].push_back(i);
		++cnt[a[i]];
	}

	for (int i = 1; i <= m; i++) {
		ans[i] = 1e9;
		++cntOcc[cnt[i]];
		mx = max(mx, cnt[i]);
	}

	for (int i = 1; i <= n; i += 2) {
		if (i == n) {
			pairing[i] = 0;
		}
		else {
			pairing[i] = i + 1;
			pairing[i + 1] = i;
		}
	}

	solve();

	pairing[1] = 0;
	for (int i = 2; i <= n; i += 2) {
		if (i == n) {
			pairing[i] = 0;
		}
		else {
			pairing[i] = i + 1;
			pairing[i + 1] = i;
		}
	}

	solve();
 
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << "\n";
	}
}

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