Submission #173184

#	Time	Username	Problem	Language	Result	Execution time	Memory
173184		songc	Rope (JOI17_rope)	C++14	100 / 100	791 ms	41484 KiB

rope

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
int A[1010101];
int Ecnt[1010101], E[1010101], EM, ES, EN=1;
int Ocnt[1010101], O[1010101], OM, OS, ON=1;
pii Ec[1010101], Oc[1010101];

int Eup(int k, int v){
	Ecnt[E[k]]--;
	if (v < 0 ){
		if (!Ecnt[EM]) EM--;
		else if (EM == ES && Ecnt[EM]<=1) ES--;
		else if (!Ecnt[ES]) ES--;
	}
	E[k] += v;
	if (v > 0){
		if (EM < E[k]) EM = E[k];
		else if (ES < E[k]) ES = E[k];
	}
	Ecnt[E[k]]++;
}

int Oup(int k, int v){
	Ocnt[O[k]]--;
	if (v < 0){
		if (!Ocnt[OM]) OM--;
		else if (OM == OS && Ocnt[OM]<=1) OS--;
		else if (!Ocnt[OS]) OS--;
	}
	O[k] += v;
	if (v > 0){
		if (OM < O[k]) OM = O[k];
		else if (OS < O[k]) OS = O[k];
	}
	Ocnt[O[k]]++;
}

int main(){
	scanf("%d %d", &N, &M);
	if (M == 1){
		puts("0");
		return 0;
	}
	Ecnt[0]=Ocnt[0]=M;
	for (int i=1; i<=N; i++) scanf("%d", &A[i]);

	for (int i=1; i+1<=N; i+=2){
		Eup(A[i], 1);
		Eup(A[i+1], 1);
		if (A[i] != A[i+1]){
			Ec[EN++] = pii(A[i], A[i+1]);
			Ec[EN++] = pii(A[i+1], A[i]);
		}
	}
	for (int i=2; i+1<=N; i+=2){
		Oup(A[i], 1);
		Oup(A[i+1], 1);
		if (A[i] != A[i+1]){
			Oc[ON++] = pii(A[i], A[i+1]);
			Oc[ON++] = pii(A[i+1], A[i]);
		}
	}

	if (N & 1){
		Eup(A[N], 1);
		Oup(A[1], 1);
	}
	else{
		Oup(A[1], 1);
		Oup(A[N], 1);
	}
	sort(Ec+1, Ec+EN);
	sort(Oc+1, Oc+ON);

	int te=1, to=1; 
	for (int i=1; i<=M; i++){
		int ans=0;
		for (int j=te; j<EN && Ec[j].first==i; j++) Eup(Ec[j].second, -1);
		for (int j=to; j<ON && Oc[j].first==i; j++) Oup(Oc[j].second, -1);

		if (E[i] == EM) ans = max(ans, E[i]+ES);
		else ans = max(ans, E[i]+EM);
		if (O[i] == OM) ans = max(ans, O[i]+OS);
		else ans = max(ans, O[i]+OM);
		printf("%d\n", N-ans);

		for (; te<EN && Ec[te].first==i; te++) Eup(Ec[te].second, 1);
		for (; to<ON && Oc[to].first==i; to++) Oup(Oc[to].second, 1);
	}
	return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int Eup(int, int)':
rope.cpp:25:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
rope.cpp: In function 'int Oup(int, int)':
rope.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
rope.cpp: In function 'int main()':
rope.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%d", &A[i]);
                           ~~~~~^~~~~~~~~~~~~

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