Submission #256310

#	Time	Username	Problem	Language	Result	Execution time	Memory
256310		pit4h	Rope (JOI17_rope)	C++14	100 / 100	1092 ms	89580 KiB

rope

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin>>n>>m;
	vector<int> a(n), occ(m+1);
	vector<vector<pair<int, int>>> col(m+1);
	vector<pair<int, int>> best;
	for(int i=0; i<n; ++i) {
		cin>>a[i];
		occ[a[i]]++;
		if(i==0 || a[i] != a[i-1]) {
			col[a[i]].push_back({i, i});
		}
		else {
			col[a[i]].back().nd = i;
		}
	}
	for(int i=1; i<=m; ++i) {
		best.push_back({occ[i], i});
	}
	sort(best.rbegin(), best.rend());
	vector<vector<int>> cnt(2, vector<int>(m+1));
	for(int c=1; c<=m; ++c) {
		if(col[c].empty()) continue;
		
		vector<int> prv(2);
		vector<bool> fail(2);

		int beg = col[c][0].st;
		int end = col[c][0].nd;
		if(end==n-1) {
			int ans = n;
			for(int i=0; i<min(m, 2); ++i) {
				if(c==best[i].nd) ans=min(ans, n-occ[c]);
				else ans = min(ans, n-occ[c]-occ[best[i].nd]);
			}
			cout<<ans<<'\n';
			continue;
		}
		if((end-beg+1)%2==1) {
			if(beg==0) {
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
			else {
				cnt[0][a[beg-1]] = 1;
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
		}
		else {
			if(beg==0) {
				prv[0] = end;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
			else {
				prv[0] = end;
				cnt[1][a[beg-1]] = 1;
				cnt[1][a[end+1]] = 1;
				prv[1] = end+1;
			}
		}
		for(int it=0; it<=1; ++it) {
			bool start=0;
			for(auto cur: col[c]) {
				if(!start) {
					start=1;
					continue;
				}
				beg = cur.st;
				end = cur.nd;
				if((beg-prv[it])%2==0) {
					beg--;
					cnt[it][a[beg]]++;
				}
				if((end-beg+1)%2==1 && end != n-1) {
					end++;
					cnt[it][a[end]]++;
				}
				prv[it] = end;
			}
		}
		int ans = n;
		for(int j=0; j<min(m, (int)col[c].size()+1); ++j) {
			int i = best[j].nd;
			if(c==i) {
				ans = min(ans, n-occ[c]);
			}
			else {
				if(!fail[0]) ans = min(ans, n - occ[c] - occ[i] + cnt[0][i]);
				if(!fail[1]) ans = min(ans, n - occ[c] - occ[i] + cnt[1][i]);
			}
		}
		cout<<ans<<'\n';

		for(auto i: col[c]) {
			if(i.st != 0) cnt[0][a[i.st-1]]=cnt[1][a[i.st-1]]=0;
			if(i.nd != n-1) cnt[0][a[i.nd+1]]=cnt[1][a[i.nd+1]]=0;
		}
	}
}

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