Submission #340627

#	Time	Username	Problem	Language	Result	Execution time	Memory
340627		couplefire	Rope (JOI17_rope)	C++17	100 / 100	1355 ms	86568 KiB

rope

#include <bits/stdc++.h>

const int S = 1 << 20;
char frd[S], *ihead = frd + S;
const char *itail = ihead;

inline char nxtChar()
{
	if (ihead == itail)
		fread(frd, 1, S, stdin), ihead = frd;
	return *ihead++;
}

template <class T>
inline void read(T &res)
{
	char ch; 
	while (ch = nxtChar(), !isdigit(ch));
	res = ch ^ 48;
	while (ch = nxtChar(), isdigit(ch))
		res = res * 10 + ch - 48;
} 

char fwt[S], *ohead = fwt;
const char *otail = ohead + S;

inline void outChar(char ch)
{
	if (ohead == otail)
		fwrite(fwt, 1, S, stdout), ohead = fwt;
	*ohead++ = ch;
}

template <class T>
inline void put(T x)
{
	if (x > 9)
		put(x / 10);
	outChar(x % 10 + 48);
}

using std::vector;
const int N = 1e6 + 5;
const int Maxn = 0x3f3f3f3f;

vector<int> v[N];
int n, m, mx;
int cnt[N], apr[N], ans[N], col[N], mth[N];

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
template <class T>
inline void CkMax(T &x, T y) {x < y ? x = y : 0;}

inline void del(int x)
{
	--apr[cnt[x]];
	!apr[cnt[x]] && cnt[x] == mx ? --mx : 0;
	++apr[--cnt[x]];
}

inline void add(int x)
{
	--apr[cnt[x]];
	cnt[x] == mx ? ++mx : 0;
	++apr[++cnt[x]];
}

inline void solve()
{
	for (int i = 1; i <= m; ++i)
	{
		int tmp = cnt[i];
		for (int j = 1; j <= tmp; ++j)
			del(i);
		for (int j = 0, jm = v[i].size(); j < jm; ++j)
		{
			int x = v[i][j];
			if (mth[x] && col[mth[x]] != i)
				del(col[mth[x]]);
		}
		CkMin(ans[i], n - tmp - mx);
		for (int j = 0, jm = v[i].size(); j < jm; ++j)
		{
			int x = v[i][j];
			if (mth[x] && col[mth[x]] != i)
				add(col[mth[x]]);
		}
		for (int j = 1; j <= tmp; ++j)
			add(i);
	}
}

int main()
{
	read(n); read(m);
	if (m == 1)
		return puts("0"), 0;

	for (int i = 1; i <= m; ++i)
		ans[i] = Maxn;
	for (int i = 1; i <= n; ++i)
	{
		read(col[i]);
		v[col[i]].push_back(i);
		++cnt[col[i]];
	}	
	for (int i = 1; i <= m; ++i)
		CkMax(mx, cnt[i]), ++apr[cnt[i]];
	for (int i = 1; i <= n; i += 2)
		if (i < n)
			mth[i] = i + 1, mth[i + 1] = i;
		else
			mth[i] = 0;
	solve();

	mth[1] = 0;
	for (int i = 2; i <= n; i += 2)
		if (i < n)
			mth[i] = i + 1, mth[i + 1] = i;
		else
			mth[i] = 0;
	solve();

	for (int i = 1; i <= m; ++i)
		put(ans[i]), outChar('\n');
	fwrite(fwt, 1, ohead - fwt, stdout);
	return 0;	
}

Compilation message (stderr)

rope.cpp: In function 'char nxtChar()':
rope.cpp:10:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   10 |   fread(frd, 1, S, stdin), ihead = frd;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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