Submission #489299

#	Time	Username	Problem	Language	Result	Execution time	Memory
489299		cheissmart	Rope (JOI17_rope)	C++14	100 / 100	1460 ms	96268 KiB

rope

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emaplce_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

void cmin(int& a, int b) {
	a = min(a, b);
}

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;

	vi a(n), ans(m, INF);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}

	auto go = [&] (V<array<int, 2>> x) {

		vi cnt(m), cnt2(n + 1);
		cnt2[0] = m;
		int cur_sum = 0, cur_mx = 0;
		auto add = [&] (int e) {
			cur_sum++;
			cnt2[cnt[e]]--;
			cnt[e]++;
			cnt2[cnt[e]]++;
			cur_mx = max(cur_mx, cnt[e]);
		};

		auto del = [&] (int e) {
			cur_sum--;
			cnt2[cnt[e]]--;
			cnt[e]--;
			cnt2[cnt[e]]++;
			if(cnt2[cur_mx] == 0)
				cur_mx--;
		};

		V<V<array<int, 2>>> pos(m);
		for(auto e:x) {
			pos[e[0]].PB(e), add(e[0]);
			if(e[0] == e[1]) add(e[1]);
			else if(e[1] != -1) pos[e[1]].PB(e), add(e[1]);
		}
		for(int i = 0; i < m; i++) {
			int cost = 0;
			for(auto e:pos[i]) {
				del(e[0]), cost += e[0] != i;
				if(e[1] != -1) del(e[1]), cost += e[1] != i;
			}
			cost += cur_sum - cur_mx;
			ans[i] = min(ans[i], cost);
			for(auto e:pos[i]) {
				add(e[0]);
				if(e[1] != -1) add(e[1]);
			}
		}
	};

	V<array<int, 2>> x, y;
	for(int i = 0; i < n; i += 2) {
		array<int, 2> tt;
		tt[0] = a[i], tt[1] = -1;
		if(i + 1 < n) tt[1] = a[i + 1];
		x.PB(tt);
	}
	y.PB({a[0], -1});
	for(int i = 1; i < n; i += 2) {
		array<int, 2> tt;
		tt[0] = a[i], tt[1] = -1;
		if(i + 1 < n) tt[1] = a[i + 1];
		y.PB(tt);
	}

	go(x), go(y);

	for(int i = 0; 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