// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<int> a;
vector<int> cnt;
vector<vector<int> > pr1, pr2;
set<array<int,2> > st1, st2;
void upd(int ind, int val, bool f) {
if(!f) {
auto tmp = st1.lower_bound({cnt[ind], ind});
assert(tmp != st1.end());
st1.erase(tmp);
cnt[ind] += val;
st1.insert({cnt[ind], ind});
}
else {
auto tmp = st2.lower_bound({cnt[ind], ind});
assert(tmp != st2.end());
st2.erase(tmp);
cnt[ind] += val;
st2.insert({cnt[ind], ind});
}
}
inline void solve() {
cin>>n>>m;
a.resize(n + 5);
cnt.assign(m + 5, 0);
pr1.assign(m + 5, vector<int>());
pr2.assign(m + 5, vector<int>());
st1.insert({0, 0});
st2.insert({0, 0});
for(int i = 1; i<=n; i++) {
cin >> a[i];
}
for(int i = 1; i<=n; i++) {
cnt[a[i]]++;
}
for(int i = 1; i<n; i+=2) {
if(a[i] == a[i + 1]) continue;
pr1[a[i]].pb(a[i + 1]);
pr1[a[i + 1]].pb(a[i]);
}
for(int i = 2; i<n; i+=2) {
if(a[i] == a[i + 1]) continue;
pr2[a[i]].pb(a[i + 1]);
pr2[a[i + 1]].pb(a[i]);
}
for(int i = 1; i<=m; i++) {
st1.insert({cnt[i], i});
st2.insert({cnt[i], i});
}
vector<int> res(m + 1, INF);
for(int i = 1; i<=m; i++) {
res[i] = n - cnt[i];
}
for(int i = 1; i<=m; i++) {
// Case 1
for(auto c : pr1[i]) {
upd(c, -1, 0);
}
st1.erase({cnt[i], i});
res[i] = min(res[i], n - (cnt[i] + (*prev(st1.end()))[0]));
st1.insert({cnt[i], i});
for(auto c : pr1[i]) {
upd(c, 1, 0);
}
// Case 2
for(auto c : pr2[i]) {
upd(c, -1, 1);
}
st2.erase({cnt[i], i});
res[i] = min(res[i], n - (cnt[i] + (*prev(st2.end()))[0]));
st2.insert({cnt[i], i});
for(auto c : pr2[i]) {
upd(c, 1, 1);
}
}
for(int i = 1; i<=m; i++) {
cout << res[i] << "\n";
}
}
signed main() {
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
500 KB |
Output is correct |
18 |
Correct |
1 ms |
500 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
500 KB |
Output is correct |
18 |
Correct |
1 ms |
500 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
33 ms |
2216 KB |
Output is correct |
28 |
Correct |
21 ms |
1884 KB |
Output is correct |
29 |
Correct |
32 ms |
1888 KB |
Output is correct |
30 |
Correct |
26 ms |
1628 KB |
Output is correct |
31 |
Correct |
35 ms |
2140 KB |
Output is correct |
32 |
Correct |
22 ms |
1880 KB |
Output is correct |
33 |
Correct |
31 ms |
2092 KB |
Output is correct |
34 |
Correct |
24 ms |
1628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
500 KB |
Output is correct |
18 |
Correct |
1 ms |
500 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
33 ms |
2216 KB |
Output is correct |
28 |
Correct |
21 ms |
1884 KB |
Output is correct |
29 |
Correct |
32 ms |
1888 KB |
Output is correct |
30 |
Correct |
26 ms |
1628 KB |
Output is correct |
31 |
Correct |
35 ms |
2140 KB |
Output is correct |
32 |
Correct |
22 ms |
1880 KB |
Output is correct |
33 |
Correct |
31 ms |
2092 KB |
Output is correct |
34 |
Correct |
24 ms |
1628 KB |
Output is correct |
35 |
Correct |
91 ms |
2364 KB |
Output is correct |
36 |
Correct |
90 ms |
2364 KB |
Output is correct |
37 |
Correct |
97 ms |
2312 KB |
Output is correct |
38 |
Correct |
91 ms |
2352 KB |
Output is correct |
39 |
Correct |
91 ms |
2356 KB |
Output is correct |
40 |
Correct |
79 ms |
2396 KB |
Output is correct |
41 |
Correct |
89 ms |
2788 KB |
Output is correct |
42 |
Correct |
81 ms |
2480 KB |
Output is correct |
43 |
Correct |
74 ms |
2336 KB |
Output is correct |
44 |
Correct |
79 ms |
2392 KB |
Output is correct |
45 |
Correct |
84 ms |
2528 KB |
Output is correct |
46 |
Correct |
79 ms |
2472 KB |
Output is correct |
47 |
Correct |
75 ms |
2536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
500 KB |
Output is correct |
18 |
Correct |
1 ms |
500 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
33 ms |
2216 KB |
Output is correct |
28 |
Correct |
21 ms |
1884 KB |
Output is correct |
29 |
Correct |
32 ms |
1888 KB |
Output is correct |
30 |
Correct |
26 ms |
1628 KB |
Output is correct |
31 |
Correct |
35 ms |
2140 KB |
Output is correct |
32 |
Correct |
22 ms |
1880 KB |
Output is correct |
33 |
Correct |
31 ms |
2092 KB |
Output is correct |
34 |
Correct |
24 ms |
1628 KB |
Output is correct |
35 |
Correct |
91 ms |
2364 KB |
Output is correct |
36 |
Correct |
90 ms |
2364 KB |
Output is correct |
37 |
Correct |
97 ms |
2312 KB |
Output is correct |
38 |
Correct |
91 ms |
2352 KB |
Output is correct |
39 |
Correct |
91 ms |
2356 KB |
Output is correct |
40 |
Correct |
79 ms |
2396 KB |
Output is correct |
41 |
Correct |
89 ms |
2788 KB |
Output is correct |
42 |
Correct |
81 ms |
2480 KB |
Output is correct |
43 |
Correct |
74 ms |
2336 KB |
Output is correct |
44 |
Correct |
79 ms |
2392 KB |
Output is correct |
45 |
Correct |
84 ms |
2528 KB |
Output is correct |
46 |
Correct |
79 ms |
2472 KB |
Output is correct |
47 |
Correct |
75 ms |
2536 KB |
Output is correct |
48 |
Correct |
1159 ms |
22236 KB |
Output is correct |
49 |
Correct |
1177 ms |
22232 KB |
Output is correct |
50 |
Correct |
1182 ms |
22184 KB |
Output is correct |
51 |
Correct |
1111 ms |
21684 KB |
Output is correct |
52 |
Correct |
1029 ms |
18912 KB |
Output is correct |
53 |
Correct |
1002 ms |
20544 KB |
Output is correct |
54 |
Correct |
958 ms |
18664 KB |
Output is correct |
55 |
Correct |
961 ms |
18384 KB |
Output is correct |
56 |
Correct |
901 ms |
18064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
500 KB |
Output is correct |
18 |
Correct |
1 ms |
500 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
33 ms |
2216 KB |
Output is correct |
28 |
Correct |
21 ms |
1884 KB |
Output is correct |
29 |
Correct |
32 ms |
1888 KB |
Output is correct |
30 |
Correct |
26 ms |
1628 KB |
Output is correct |
31 |
Correct |
35 ms |
2140 KB |
Output is correct |
32 |
Correct |
22 ms |
1880 KB |
Output is correct |
33 |
Correct |
31 ms |
2092 KB |
Output is correct |
34 |
Correct |
24 ms |
1628 KB |
Output is correct |
35 |
Correct |
91 ms |
2364 KB |
Output is correct |
36 |
Correct |
90 ms |
2364 KB |
Output is correct |
37 |
Correct |
97 ms |
2312 KB |
Output is correct |
38 |
Correct |
91 ms |
2352 KB |
Output is correct |
39 |
Correct |
91 ms |
2356 KB |
Output is correct |
40 |
Correct |
79 ms |
2396 KB |
Output is correct |
41 |
Correct |
89 ms |
2788 KB |
Output is correct |
42 |
Correct |
81 ms |
2480 KB |
Output is correct |
43 |
Correct |
74 ms |
2336 KB |
Output is correct |
44 |
Correct |
79 ms |
2392 KB |
Output is correct |
45 |
Correct |
84 ms |
2528 KB |
Output is correct |
46 |
Correct |
79 ms |
2472 KB |
Output is correct |
47 |
Correct |
75 ms |
2536 KB |
Output is correct |
48 |
Correct |
1159 ms |
22236 KB |
Output is correct |
49 |
Correct |
1177 ms |
22232 KB |
Output is correct |
50 |
Correct |
1182 ms |
22184 KB |
Output is correct |
51 |
Correct |
1111 ms |
21684 KB |
Output is correct |
52 |
Correct |
1029 ms |
18912 KB |
Output is correct |
53 |
Correct |
1002 ms |
20544 KB |
Output is correct |
54 |
Correct |
958 ms |
18664 KB |
Output is correct |
55 |
Correct |
961 ms |
18384 KB |
Output is correct |
56 |
Correct |
901 ms |
18064 KB |
Output is correct |
57 |
Execution timed out |
2543 ms |
222292 KB |
Time limit exceeded |
58 |
Halted |
0 ms |
0 KB |
- |