Submission #670205

#	Time	Username	Problem	Language	Result	Execution time	Memory
670205		ymm	Rope (JOI17_rope)	C++17	100 / 100	1219 ms	202168 KiB

rope

///
///   ♪ Hashire sori yo ♪
///   ♪ Kaze no you ni  ♪
///   ♪ Tsukimihara wo  ♪
///   ♪ PADORU PADORU   ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1<<20;
int a[N];
vector<pii> vec[N];
int n, m;

int cnt[N];
priority_queue<pii> pq;
vector<pii> record;
bool recording;

void add(int c, int x)
{
	if (recording)
		record.push_back({c, cnt[c]});
	cnt[c] += x;
	pq.push({cnt[c], c});
}

void revert()
{
	recording = 0;
	while (record.size()) {
		auto [c, x] = record.back();
		record.pop_back();
		add(c, x-cnt[c]);
	}
}

int get_max()
{
	while (pq.top().first != cnt[pq.top().second])
		pq.pop();
	return pq.top().first;
}

int count(int c, bool odd)
{
	recording = 1;
	int cntc = cnt[c];
	int ans = 0;
	add(c, -cntc);
	vector<pair<pii,bool>> v;
	int lst = 0;
	for (auto [l, r] : vec[c]) {
		if (lst != l)
			v.push_back({{lst, l}, 0});
		v.push_back({{l, r}, 1});
		lst = r;
	}
	if (lst != n)
		v.push_back({{lst, n}, 0});
	for (auto [lr, is] : v) {
		auto [l, r] = lr;
		if (r == n)
			break;
		odd ^= (r - l) & 1;
		if (odd) {
			++cntc;
			++ans;
			add(a[r - 1 + is], -1);
		}
	}
	ans += n - cntc - get_max();
	revert();
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		cin >> a[i];
		--a[i];
	}
	int lst = 0;
	Loop (i,0,n) {
		if (a[i] != a[lst]) {
			vec[a[lst]].push_back({lst, i});
			lst = i;
		}
		add(a[i], 1);
	}
	vec[a[lst]].push_back({lst, n});
	Loop (i,0,m) {
		int ans = min(count(i, 0), count(i, 1));
		cout << ans << '\n';
	}
}

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