# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
670203 |
2022-12-08T09:40:31 Z |
ymm |
Rope (JOI17_rope) |
C++17 |
|
2500 ms |
120184 KB |
///
/// ♪ Hashire sori yo ♪
/// ♪ Kaze no you ni ♪
/// ♪ Tsukimihara wo ♪
/// ♪ PADORU PADORU ♪
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 1<<20;
int a[N];
vector<pii> vec[N];
int n, m;
int cnt[N];
set<pii, greater<pii>> cnts;
vector<pii> record;
bool recording;
void add(int c, int x)
{
if (recording)
record.push_back({c, cnt[c]});
cnts.erase({cnt[c], c});
cnt[c] += x;
cnts.insert({cnt[c], c});
}
void revert()
{
recording = 0;
while (record.size()) {
auto [c, x] = record.back();
record.pop_back();
add(c, x-cnt[c]);
}
}
int count(int c, bool odd)
{
recording = 1;
int cntc = cnt[c];
int ans = 0;
add(c, -cntc);
vector<pair<pii,bool>> v;
int lst = 0;
for (auto [l, r] : vec[c]) {
if (lst != l)
v.push_back({{lst, l}, 0});
v.push_back({{l, r}, 1});
lst = r;
}
if (lst != n)
v.push_back({{lst, n}, 0});
for (auto [lr, is] : v) {
auto [l, r] = lr;
if (r == n)
break;
odd ^= (r - l) & 1;
if (odd) {
++cntc;
++ans;
add(a[r - 1 + is], -1);
}
}
ans += n - cntc - cnts.begin()->first;
revert();
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) {
cin >> a[i];
--a[i];
}
int lst = 0;
Loop (i,0,n) {
if (a[i] != a[lst]) {
vec[a[lst]].push_back({lst, i});
lst = i;
}
add(a[i], 1);
}
vec[a[lst]].push_back({lst, n});
Loop (i,0,m) {
int ans = min(count(i, 0), count(i, 1));
cout << ans << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
24916 KB |
Output is correct |
2 |
Correct |
13 ms |
24956 KB |
Output is correct |
3 |
Correct |
14 ms |
24872 KB |
Output is correct |
4 |
Correct |
13 ms |
24916 KB |
Output is correct |
5 |
Correct |
13 ms |
24916 KB |
Output is correct |
6 |
Correct |
13 ms |
24916 KB |
Output is correct |
7 |
Correct |
13 ms |
24928 KB |
Output is correct |
8 |
Correct |
13 ms |
24848 KB |
Output is correct |
9 |
Correct |
14 ms |
24916 KB |
Output is correct |
10 |
Correct |
14 ms |
24920 KB |
Output is correct |
11 |
Correct |
13 ms |
24916 KB |
Output is correct |
12 |
Correct |
13 ms |
24916 KB |
Output is correct |
13 |
Correct |
14 ms |
24868 KB |
Output is correct |
14 |
Correct |
13 ms |
24960 KB |
Output is correct |
15 |
Correct |
13 ms |
24956 KB |
Output is correct |
16 |
Correct |
13 ms |
24916 KB |
Output is correct |
17 |
Correct |
13 ms |
24916 KB |
Output is correct |
18 |
Correct |
14 ms |
24956 KB |
Output is correct |
19 |
Correct |
13 ms |
24856 KB |
Output is correct |
20 |
Correct |
14 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24916 KB |
Output is correct |
22 |
Correct |
14 ms |
24916 KB |
Output is correct |
23 |
Correct |
13 ms |
24964 KB |
Output is correct |
24 |
Correct |
13 ms |
24852 KB |
Output is correct |
25 |
Correct |
13 ms |
24916 KB |
Output is correct |
26 |
Correct |
13 ms |
24916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
24916 KB |
Output is correct |
2 |
Correct |
13 ms |
24956 KB |
Output is correct |
3 |
Correct |
14 ms |
24872 KB |
Output is correct |
4 |
Correct |
13 ms |
24916 KB |
Output is correct |
5 |
Correct |
13 ms |
24916 KB |
Output is correct |
6 |
Correct |
13 ms |
24916 KB |
Output is correct |
7 |
Correct |
13 ms |
24928 KB |
Output is correct |
8 |
Correct |
13 ms |
24848 KB |
Output is correct |
9 |
Correct |
14 ms |
24916 KB |
Output is correct |
10 |
Correct |
14 ms |
24920 KB |
Output is correct |
11 |
Correct |
13 ms |
24916 KB |
Output is correct |
12 |
Correct |
13 ms |
24916 KB |
Output is correct |
13 |
Correct |
14 ms |
24868 KB |
Output is correct |
14 |
Correct |
13 ms |
24960 KB |
Output is correct |
15 |
Correct |
13 ms |
24956 KB |
Output is correct |
16 |
Correct |
13 ms |
24916 KB |
Output is correct |
17 |
Correct |
13 ms |
24916 KB |
Output is correct |
18 |
Correct |
14 ms |
24956 KB |
Output is correct |
19 |
Correct |
13 ms |
24856 KB |
Output is correct |
20 |
Correct |
14 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24916 KB |
Output is correct |
22 |
Correct |
14 ms |
24916 KB |
Output is correct |
23 |
Correct |
13 ms |
24964 KB |
Output is correct |
24 |
Correct |
13 ms |
24852 KB |
Output is correct |
25 |
Correct |
13 ms |
24916 KB |
Output is correct |
26 |
Correct |
13 ms |
24916 KB |
Output is correct |
27 |
Correct |
65 ms |
27324 KB |
Output is correct |
28 |
Correct |
47 ms |
27620 KB |
Output is correct |
29 |
Correct |
61 ms |
27100 KB |
Output is correct |
30 |
Correct |
51 ms |
27168 KB |
Output is correct |
31 |
Correct |
63 ms |
27228 KB |
Output is correct |
32 |
Correct |
49 ms |
27456 KB |
Output is correct |
33 |
Correct |
64 ms |
27288 KB |
Output is correct |
34 |
Correct |
52 ms |
27116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
24916 KB |
Output is correct |
2 |
Correct |
13 ms |
24956 KB |
Output is correct |
3 |
Correct |
14 ms |
24872 KB |
Output is correct |
4 |
Correct |
13 ms |
24916 KB |
Output is correct |
5 |
Correct |
13 ms |
24916 KB |
Output is correct |
6 |
Correct |
13 ms |
24916 KB |
Output is correct |
7 |
Correct |
13 ms |
24928 KB |
Output is correct |
8 |
Correct |
13 ms |
24848 KB |
Output is correct |
9 |
Correct |
14 ms |
24916 KB |
Output is correct |
10 |
Correct |
14 ms |
24920 KB |
Output is correct |
11 |
Correct |
13 ms |
24916 KB |
Output is correct |
12 |
Correct |
13 ms |
24916 KB |
Output is correct |
13 |
Correct |
14 ms |
24868 KB |
Output is correct |
14 |
Correct |
13 ms |
24960 KB |
Output is correct |
15 |
Correct |
13 ms |
24956 KB |
Output is correct |
16 |
Correct |
13 ms |
24916 KB |
Output is correct |
17 |
Correct |
13 ms |
24916 KB |
Output is correct |
18 |
Correct |
14 ms |
24956 KB |
Output is correct |
19 |
Correct |
13 ms |
24856 KB |
Output is correct |
20 |
Correct |
14 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24916 KB |
Output is correct |
22 |
Correct |
14 ms |
24916 KB |
Output is correct |
23 |
Correct |
13 ms |
24964 KB |
Output is correct |
24 |
Correct |
13 ms |
24852 KB |
Output is correct |
25 |
Correct |
13 ms |
24916 KB |
Output is correct |
26 |
Correct |
13 ms |
24916 KB |
Output is correct |
27 |
Correct |
65 ms |
27324 KB |
Output is correct |
28 |
Correct |
47 ms |
27620 KB |
Output is correct |
29 |
Correct |
61 ms |
27100 KB |
Output is correct |
30 |
Correct |
51 ms |
27168 KB |
Output is correct |
31 |
Correct |
63 ms |
27228 KB |
Output is correct |
32 |
Correct |
49 ms |
27456 KB |
Output is correct |
33 |
Correct |
64 ms |
27288 KB |
Output is correct |
34 |
Correct |
52 ms |
27116 KB |
Output is correct |
35 |
Correct |
138 ms |
26816 KB |
Output is correct |
36 |
Correct |
138 ms |
26912 KB |
Output is correct |
37 |
Correct |
141 ms |
26824 KB |
Output is correct |
38 |
Correct |
139 ms |
26792 KB |
Output is correct |
39 |
Correct |
137 ms |
26884 KB |
Output is correct |
40 |
Correct |
124 ms |
27092 KB |
Output is correct |
41 |
Correct |
127 ms |
27100 KB |
Output is correct |
42 |
Correct |
118 ms |
27036 KB |
Output is correct |
43 |
Correct |
117 ms |
27084 KB |
Output is correct |
44 |
Correct |
131 ms |
27072 KB |
Output is correct |
45 |
Correct |
125 ms |
27088 KB |
Output is correct |
46 |
Correct |
119 ms |
27008 KB |
Output is correct |
47 |
Correct |
121 ms |
27012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
24916 KB |
Output is correct |
2 |
Correct |
13 ms |
24956 KB |
Output is correct |
3 |
Correct |
14 ms |
24872 KB |
Output is correct |
4 |
Correct |
13 ms |
24916 KB |
Output is correct |
5 |
Correct |
13 ms |
24916 KB |
Output is correct |
6 |
Correct |
13 ms |
24916 KB |
Output is correct |
7 |
Correct |
13 ms |
24928 KB |
Output is correct |
8 |
Correct |
13 ms |
24848 KB |
Output is correct |
9 |
Correct |
14 ms |
24916 KB |
Output is correct |
10 |
Correct |
14 ms |
24920 KB |
Output is correct |
11 |
Correct |
13 ms |
24916 KB |
Output is correct |
12 |
Correct |
13 ms |
24916 KB |
Output is correct |
13 |
Correct |
14 ms |
24868 KB |
Output is correct |
14 |
Correct |
13 ms |
24960 KB |
Output is correct |
15 |
Correct |
13 ms |
24956 KB |
Output is correct |
16 |
Correct |
13 ms |
24916 KB |
Output is correct |
17 |
Correct |
13 ms |
24916 KB |
Output is correct |
18 |
Correct |
14 ms |
24956 KB |
Output is correct |
19 |
Correct |
13 ms |
24856 KB |
Output is correct |
20 |
Correct |
14 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24916 KB |
Output is correct |
22 |
Correct |
14 ms |
24916 KB |
Output is correct |
23 |
Correct |
13 ms |
24964 KB |
Output is correct |
24 |
Correct |
13 ms |
24852 KB |
Output is correct |
25 |
Correct |
13 ms |
24916 KB |
Output is correct |
26 |
Correct |
13 ms |
24916 KB |
Output is correct |
27 |
Correct |
65 ms |
27324 KB |
Output is correct |
28 |
Correct |
47 ms |
27620 KB |
Output is correct |
29 |
Correct |
61 ms |
27100 KB |
Output is correct |
30 |
Correct |
51 ms |
27168 KB |
Output is correct |
31 |
Correct |
63 ms |
27228 KB |
Output is correct |
32 |
Correct |
49 ms |
27456 KB |
Output is correct |
33 |
Correct |
64 ms |
27288 KB |
Output is correct |
34 |
Correct |
52 ms |
27116 KB |
Output is correct |
35 |
Correct |
138 ms |
26816 KB |
Output is correct |
36 |
Correct |
138 ms |
26912 KB |
Output is correct |
37 |
Correct |
141 ms |
26824 KB |
Output is correct |
38 |
Correct |
139 ms |
26792 KB |
Output is correct |
39 |
Correct |
137 ms |
26884 KB |
Output is correct |
40 |
Correct |
124 ms |
27092 KB |
Output is correct |
41 |
Correct |
127 ms |
27100 KB |
Output is correct |
42 |
Correct |
118 ms |
27036 KB |
Output is correct |
43 |
Correct |
117 ms |
27084 KB |
Output is correct |
44 |
Correct |
131 ms |
27072 KB |
Output is correct |
45 |
Correct |
125 ms |
27088 KB |
Output is correct |
46 |
Correct |
119 ms |
27008 KB |
Output is correct |
47 |
Correct |
121 ms |
27012 KB |
Output is correct |
48 |
Correct |
1653 ms |
47060 KB |
Output is correct |
49 |
Correct |
1663 ms |
46924 KB |
Output is correct |
50 |
Correct |
1647 ms |
46908 KB |
Output is correct |
51 |
Correct |
1505 ms |
46444 KB |
Output is correct |
52 |
Correct |
1419 ms |
43444 KB |
Output is correct |
53 |
Correct |
1314 ms |
45388 KB |
Output is correct |
54 |
Correct |
1224 ms |
43456 KB |
Output is correct |
55 |
Correct |
1195 ms |
43084 KB |
Output is correct |
56 |
Correct |
1168 ms |
42400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
24916 KB |
Output is correct |
2 |
Correct |
13 ms |
24956 KB |
Output is correct |
3 |
Correct |
14 ms |
24872 KB |
Output is correct |
4 |
Correct |
13 ms |
24916 KB |
Output is correct |
5 |
Correct |
13 ms |
24916 KB |
Output is correct |
6 |
Correct |
13 ms |
24916 KB |
Output is correct |
7 |
Correct |
13 ms |
24928 KB |
Output is correct |
8 |
Correct |
13 ms |
24848 KB |
Output is correct |
9 |
Correct |
14 ms |
24916 KB |
Output is correct |
10 |
Correct |
14 ms |
24920 KB |
Output is correct |
11 |
Correct |
13 ms |
24916 KB |
Output is correct |
12 |
Correct |
13 ms |
24916 KB |
Output is correct |
13 |
Correct |
14 ms |
24868 KB |
Output is correct |
14 |
Correct |
13 ms |
24960 KB |
Output is correct |
15 |
Correct |
13 ms |
24956 KB |
Output is correct |
16 |
Correct |
13 ms |
24916 KB |
Output is correct |
17 |
Correct |
13 ms |
24916 KB |
Output is correct |
18 |
Correct |
14 ms |
24956 KB |
Output is correct |
19 |
Correct |
13 ms |
24856 KB |
Output is correct |
20 |
Correct |
14 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24916 KB |
Output is correct |
22 |
Correct |
14 ms |
24916 KB |
Output is correct |
23 |
Correct |
13 ms |
24964 KB |
Output is correct |
24 |
Correct |
13 ms |
24852 KB |
Output is correct |
25 |
Correct |
13 ms |
24916 KB |
Output is correct |
26 |
Correct |
13 ms |
24916 KB |
Output is correct |
27 |
Correct |
65 ms |
27324 KB |
Output is correct |
28 |
Correct |
47 ms |
27620 KB |
Output is correct |
29 |
Correct |
61 ms |
27100 KB |
Output is correct |
30 |
Correct |
51 ms |
27168 KB |
Output is correct |
31 |
Correct |
63 ms |
27228 KB |
Output is correct |
32 |
Correct |
49 ms |
27456 KB |
Output is correct |
33 |
Correct |
64 ms |
27288 KB |
Output is correct |
34 |
Correct |
52 ms |
27116 KB |
Output is correct |
35 |
Correct |
138 ms |
26816 KB |
Output is correct |
36 |
Correct |
138 ms |
26912 KB |
Output is correct |
37 |
Correct |
141 ms |
26824 KB |
Output is correct |
38 |
Correct |
139 ms |
26792 KB |
Output is correct |
39 |
Correct |
137 ms |
26884 KB |
Output is correct |
40 |
Correct |
124 ms |
27092 KB |
Output is correct |
41 |
Correct |
127 ms |
27100 KB |
Output is correct |
42 |
Correct |
118 ms |
27036 KB |
Output is correct |
43 |
Correct |
117 ms |
27084 KB |
Output is correct |
44 |
Correct |
131 ms |
27072 KB |
Output is correct |
45 |
Correct |
125 ms |
27088 KB |
Output is correct |
46 |
Correct |
119 ms |
27008 KB |
Output is correct |
47 |
Correct |
121 ms |
27012 KB |
Output is correct |
48 |
Correct |
1653 ms |
47060 KB |
Output is correct |
49 |
Correct |
1663 ms |
46924 KB |
Output is correct |
50 |
Correct |
1647 ms |
46908 KB |
Output is correct |
51 |
Correct |
1505 ms |
46444 KB |
Output is correct |
52 |
Correct |
1419 ms |
43444 KB |
Output is correct |
53 |
Correct |
1314 ms |
45388 KB |
Output is correct |
54 |
Correct |
1224 ms |
43456 KB |
Output is correct |
55 |
Correct |
1195 ms |
43084 KB |
Output is correct |
56 |
Correct |
1168 ms |
42400 KB |
Output is correct |
57 |
Execution timed out |
2558 ms |
120184 KB |
Time limit exceeded |
58 |
Halted |
0 ms |
0 KB |
- |