Submission #340627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340627	2020-12-28T03:45:01 Z	couplefire	Rope (JOI17_rope)	C++17	100 / 100	1355 ms	86568 KB

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

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	15 ms	23788 KB	Output is correct
3	Correct	15 ms	23808 KB	Output is correct
4	Correct	15 ms	23788 KB	Output is correct
5	Correct	15 ms	23788 KB	Output is correct
6	Correct	17 ms	23788 KB	Output is correct
7	Correct	15 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	15 ms	23788 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	15 ms	23808 KB	Output is correct
12	Correct	16 ms	23788 KB	Output is correct
13	Correct	16 ms	23788 KB	Output is correct
14	Correct	15 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	16 ms	23788 KB	Output is correct
17	Correct	16 ms	23916 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	15 ms	23788 KB	Output is correct
20	Correct	15 ms	23916 KB	Output is correct
21	Correct	15 ms	23788 KB	Output is correct
22	Correct	16 ms	23808 KB	Output is correct
23	Correct	15 ms	23788 KB	Output is correct
24	Correct	15 ms	23788 KB	Output is correct
25	Correct	17 ms	23788 KB	Output is correct
26	Correct	18 ms	23788 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	15 ms	23788 KB	Output is correct
3	Correct	15 ms	23808 KB	Output is correct
4	Correct	15 ms	23788 KB	Output is correct
5	Correct	15 ms	23788 KB	Output is correct
6	Correct	17 ms	23788 KB	Output is correct
7	Correct	15 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	15 ms	23788 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	15 ms	23808 KB	Output is correct
12	Correct	16 ms	23788 KB	Output is correct
13	Correct	16 ms	23788 KB	Output is correct
14	Correct	15 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	16 ms	23788 KB	Output is correct
17	Correct	16 ms	23916 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	15 ms	23788 KB	Output is correct
20	Correct	15 ms	23916 KB	Output is correct
21	Correct	15 ms	23788 KB	Output is correct
22	Correct	16 ms	23808 KB	Output is correct
23	Correct	15 ms	23788 KB	Output is correct
24	Correct	15 ms	23788 KB	Output is correct
25	Correct	17 ms	23788 KB	Output is correct
26	Correct	18 ms	23788 KB	Output is correct
27	Correct	25 ms	25708 KB	Output is correct
28	Correct	24 ms	25708 KB	Output is correct
29	Correct	23 ms	25708 KB	Output is correct
30	Correct	24 ms	25728 KB	Output is correct
31	Correct	24 ms	25708 KB	Output is correct
32	Correct	24 ms	25728 KB	Output is correct
33	Correct	23 ms	25580 KB	Output is correct
34	Correct	25 ms	25768 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	15 ms	23788 KB	Output is correct
3	Correct	15 ms	23808 KB	Output is correct
4	Correct	15 ms	23788 KB	Output is correct
5	Correct	15 ms	23788 KB	Output is correct
6	Correct	17 ms	23788 KB	Output is correct
7	Correct	15 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	15 ms	23788 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	15 ms	23808 KB	Output is correct
12	Correct	16 ms	23788 KB	Output is correct
13	Correct	16 ms	23788 KB	Output is correct
14	Correct	15 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	16 ms	23788 KB	Output is correct
17	Correct	16 ms	23916 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	15 ms	23788 KB	Output is correct
20	Correct	15 ms	23916 KB	Output is correct
21	Correct	15 ms	23788 KB	Output is correct
22	Correct	16 ms	23808 KB	Output is correct
23	Correct	15 ms	23788 KB	Output is correct
24	Correct	15 ms	23788 KB	Output is correct
25	Correct	17 ms	23788 KB	Output is correct
26	Correct	18 ms	23788 KB	Output is correct
27	Correct	25 ms	25708 KB	Output is correct
28	Correct	24 ms	25708 KB	Output is correct
29	Correct	23 ms	25708 KB	Output is correct
30	Correct	24 ms	25728 KB	Output is correct
31	Correct	24 ms	25708 KB	Output is correct
32	Correct	24 ms	25728 KB	Output is correct
33	Correct	23 ms	25580 KB	Output is correct
34	Correct	25 ms	25768 KB	Output is correct
35	Correct	35 ms	25964 KB	Output is correct
36	Correct	33 ms	26092 KB	Output is correct
37	Correct	31 ms	25964 KB	Output is correct
38	Correct	30 ms	25964 KB	Output is correct
39	Correct	30 ms	25964 KB	Output is correct
40	Correct	28 ms	26092 KB	Output is correct
41	Correct	27 ms	26092 KB	Output is correct
42	Correct	30 ms	26112 KB	Output is correct
43	Correct	26 ms	26092 KB	Output is correct
44	Correct	25 ms	26092 KB	Output is correct
45	Correct	29 ms	26092 KB	Output is correct
46	Correct	29 ms	25964 KB	Output is correct
47	Correct	29 ms	26092 KB	Output is correct

Subtask #4
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	15 ms	23788 KB	Output is correct
3	Correct	15 ms	23808 KB	Output is correct
4	Correct	15 ms	23788 KB	Output is correct
5	Correct	15 ms	23788 KB	Output is correct
6	Correct	17 ms	23788 KB	Output is correct
7	Correct	15 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	15 ms	23788 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	15 ms	23808 KB	Output is correct
12	Correct	16 ms	23788 KB	Output is correct
13	Correct	16 ms	23788 KB	Output is correct
14	Correct	15 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	16 ms	23788 KB	Output is correct
17	Correct	16 ms	23916 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	15 ms	23788 KB	Output is correct
20	Correct	15 ms	23916 KB	Output is correct
21	Correct	15 ms	23788 KB	Output is correct
22	Correct	16 ms	23808 KB	Output is correct
23	Correct	15 ms	23788 KB	Output is correct
24	Correct	15 ms	23788 KB	Output is correct
25	Correct	17 ms	23788 KB	Output is correct
26	Correct	18 ms	23788 KB	Output is correct
27	Correct	25 ms	25708 KB	Output is correct
28	Correct	24 ms	25708 KB	Output is correct
29	Correct	23 ms	25708 KB	Output is correct
30	Correct	24 ms	25728 KB	Output is correct
31	Correct	24 ms	25708 KB	Output is correct
32	Correct	24 ms	25728 KB	Output is correct
33	Correct	23 ms	25580 KB	Output is correct
34	Correct	25 ms	25768 KB	Output is correct
35	Correct	35 ms	25964 KB	Output is correct
36	Correct	33 ms	26092 KB	Output is correct
37	Correct	31 ms	25964 KB	Output is correct
38	Correct	30 ms	25964 KB	Output is correct
39	Correct	30 ms	25964 KB	Output is correct
40	Correct	28 ms	26092 KB	Output is correct
41	Correct	27 ms	26092 KB	Output is correct
42	Correct	30 ms	26112 KB	Output is correct
43	Correct	26 ms	26092 KB	Output is correct
44	Correct	25 ms	26092 KB	Output is correct
45	Correct	29 ms	26092 KB	Output is correct
46	Correct	29 ms	25964 KB	Output is correct
47	Correct	29 ms	26092 KB	Output is correct
48	Correct	460 ms	44012 KB	Output is correct
49	Correct	521 ms	43972 KB	Output is correct
50	Correct	428 ms	44012 KB	Output is correct
51	Correct	480 ms	43628 KB	Output is correct
52	Correct	491 ms	42348 KB	Output is correct
53	Correct	239 ms	43392 KB	Output is correct
54	Correct	193 ms	42220 KB	Output is correct
55	Correct	183 ms	42112 KB	Output is correct
56	Correct	167 ms	41708 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	15 ms	23788 KB	Output is correct
3	Correct	15 ms	23808 KB	Output is correct
4	Correct	15 ms	23788 KB	Output is correct
5	Correct	15 ms	23788 KB	Output is correct
6	Correct	17 ms	23788 KB	Output is correct
7	Correct	15 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	15 ms	23788 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	15 ms	23808 KB	Output is correct
12	Correct	16 ms	23788 KB	Output is correct
13	Correct	16 ms	23788 KB	Output is correct
14	Correct	15 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	16 ms	23788 KB	Output is correct
17	Correct	16 ms	23916 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	15 ms	23788 KB	Output is correct
20	Correct	15 ms	23916 KB	Output is correct
21	Correct	15 ms	23788 KB	Output is correct
22	Correct	16 ms	23808 KB	Output is correct
23	Correct	15 ms	23788 KB	Output is correct
24	Correct	15 ms	23788 KB	Output is correct
25	Correct	17 ms	23788 KB	Output is correct
26	Correct	18 ms	23788 KB	Output is correct
27	Correct	25 ms	25708 KB	Output is correct
28	Correct	24 ms	25708 KB	Output is correct
29	Correct	23 ms	25708 KB	Output is correct
30	Correct	24 ms	25728 KB	Output is correct
31	Correct	24 ms	25708 KB	Output is correct
32	Correct	24 ms	25728 KB	Output is correct
33	Correct	23 ms	25580 KB	Output is correct
34	Correct	25 ms	25768 KB	Output is correct
35	Correct	35 ms	25964 KB	Output is correct
36	Correct	33 ms	26092 KB	Output is correct
37	Correct	31 ms	25964 KB	Output is correct
38	Correct	30 ms	25964 KB	Output is correct
39	Correct	30 ms	25964 KB	Output is correct
40	Correct	28 ms	26092 KB	Output is correct
41	Correct	27 ms	26092 KB	Output is correct
42	Correct	30 ms	26112 KB	Output is correct
43	Correct	26 ms	26092 KB	Output is correct
44	Correct	25 ms	26092 KB	Output is correct
45	Correct	29 ms	26092 KB	Output is correct
46	Correct	29 ms	25964 KB	Output is correct
47	Correct	29 ms	26092 KB	Output is correct
48	Correct	460 ms	44012 KB	Output is correct
49	Correct	521 ms	43972 KB	Output is correct
50	Correct	428 ms	44012 KB	Output is correct
51	Correct	480 ms	43628 KB	Output is correct
52	Correct	491 ms	42348 KB	Output is correct
53	Correct	239 ms	43392 KB	Output is correct
54	Correct	193 ms	42220 KB	Output is correct
55	Correct	183 ms	42112 KB	Output is correct
56	Correct	167 ms	41708 KB	Output is correct
57	Correct	1355 ms	86568 KB	Output is correct
58	Correct	1217 ms	68084 KB	Output is correct
59	Correct	1169 ms	68100 KB	Output is correct
60	Correct	1222 ms	72812 KB	Output is correct
61	Correct	1213 ms	72940 KB	Output is correct
62	Correct	519 ms	57196 KB	Output is correct
63	Correct	787 ms	62444 KB	Output is correct
64	Correct	632 ms	59176 KB	Output is correct
65	Correct	313 ms	50796 KB	Output is correct

Submission #340627

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 10.0 / 10.0

Subtask #4 25.0 / 25.0

Subtask #5 20.0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
10.0 / 10.0

Subtask #4
25.0 / 25.0

Subtask #5
20.0 / 20.0