Submission #128880

#	Time	Username	Problem	Language	Result	Execution time	Memory
128880		youngyojun	Rope (JOI17_rope)	C++11	100 / 100	1212 ms	92108 KiB

rope

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MAXN = 1000055;

int D[MAXN][2];
bitset<MAXN> chk;

vector<int> G[MAXN];
int O[MAXN];
int A[MAXN], B[MAXN];

int N, M;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		B[A[i]]++;
	}
	for(int i = 1; i <= M; i++) G[B[i]].eb(i);
	for(int i = N, c = 0; i; i--)
		for(int v : G[i]) O[++c] = v;
	for(int i = 0; i <= N; i++) G[i].clear();
	for(int i = 1; i < N; i++) if(A[i] != A[i+1]) {
		G[A[i]].eb(i+1);
		G[A[i+1]].eb(-i);
	}

	for(int i = 1; i <= M; i++) {
		int ret = 0, dg = 0;
		for(int v : G[i]) {
			D[A[abs(v)]][(0 < v ? v-1 : -v)&1]++;
			chk[A[abs(v)]] = true;
			dg++;
		}
		for(int oi = 1, c; oi <= M && oi <= dg+2; oi++) {
			c = O[oi];
			if(c == i || chk[c]) continue;
			ret = -B[c];
			break;
		}
		for(int v : G[i]) {
			int c = A[abs(v)], t = min(D[c][0], D[c][1]) - B[c];
			if(t < ret) ret = t;
		}
		for(int v : G[i]) {
			D[A[abs(v)]][(0 < v ? v-1 : -v)&1] = 0;
			chk[A[abs(v)]] = false;
		}
		printf("%d\n", ret + N-B[i]);
	}
	return 0;
}

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