oj.uz

Submission #599081

# Submission time Handle Problem Language Result Execution time Memory
599081 2022-07-19T09:56:02 Z piOOE Rope (JOI17_rope) C++17
80 / 100
 2500 ms 155664 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1000000, M = 10000000;

int a[N], ans[M], cnt[M];

vector<int> g[N];
set<pair<int, int>> st;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(ans, 0x3f, sizeof(ans));
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
    ++cnt[a[i]];
  }
  for (int i = 0; i < m; ++i) {
    st.insert({cnt[i], i});
  }
  for (int k = 0; k < 2; ++k) {
    for (int i = 0; i < m; ++i) {
      g[i].clear();
    }
    for (int i = k; i + 1 < n; i += 2) {
      if (a[i] != a[i + 1]) {
        g[a[i]].push_back(a[i + 1]);
        g[a[i + 1]].push_back(a[i]);
      }
    }
    for (int c = 0; c < m; ++c) {
      int now = cnt[c];
      auto upd = [](int v, int nw) {
        st.erase({cnt[v], v});
        st.insert({cnt[v] = nw, v});
      };
      upd(c, 0);
      for (int to : g[c]) {
        upd(to, cnt[to] - 1);
      }
      ans[c] = min(ans[c], n - now - st.rbegin()->first);
      upd(c, now);
      for (int to : g[c]) {
        upd(to, cnt[to] + 1);
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 30 ms 62948 KB Output is correct
4 Correct 35 ms 62948 KB Output is correct
5 Correct 29 ms 62936 KB Output is correct
6 Correct 31 ms 62892 KB Output is correct
7 Correct 33 ms 62856 KB Output is correct
8 Correct 31 ms 62940 KB Output is correct
9 Correct 30 ms 62940 KB Output is correct
10 Correct 30 ms 62920 KB Output is correct
11 Correct 31 ms 62920 KB Output is correct
12 Correct 30 ms 62928 KB Output is correct
13 Correct 31 ms 62888 KB Output is correct
14 Correct 31 ms 62896 KB Output is correct
15 Correct 31 ms 62840 KB Output is correct
16 Correct 31 ms 62904 KB Output is correct
17 Correct 38 ms 62888 KB Output is correct
18 Correct 29 ms 62824 KB Output is correct
19 Correct 30 ms 62844 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 37 ms 62932 KB Output is correct
22 Correct 29 ms 62932 KB Output is correct
23 Correct 29 ms 62844 KB Output is correct
24 Correct 29 ms 62832 KB Output is correct
25 Correct 31 ms 62896 KB Output is correct
26 Correct 30 ms 62880 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 30 ms 62948 KB Output is correct
4 Correct 35 ms 62948 KB Output is correct
5 Correct 29 ms 62936 KB Output is correct
6 Correct 31 ms 62892 KB Output is correct
7 Correct 33 ms 62856 KB Output is correct
8 Correct 31 ms 62940 KB Output is correct
9 Correct 30 ms 62940 KB Output is correct
10 Correct 30 ms 62920 KB Output is correct
11 Correct 31 ms 62920 KB Output is correct
12 Correct 30 ms 62928 KB Output is correct
13 Correct 31 ms 62888 KB Output is correct
14 Correct 31 ms 62896 KB Output is correct
15 Correct 31 ms 62840 KB Output is correct
16 Correct 31 ms 62904 KB Output is correct
17 Correct 38 ms 62888 KB Output is correct
18 Correct 29 ms 62824 KB Output is correct
19 Correct 30 ms 62844 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 37 ms 62932 KB Output is correct
22 Correct 29 ms 62932 KB Output is correct
23 Correct 29 ms 62844 KB Output is correct
24 Correct 29 ms 62832 KB Output is correct
25 Correct 31 ms 62896 KB Output is correct
26 Correct 30 ms 62880 KB Output is correct
27 Correct 73 ms 64200 KB Output is correct
28 Correct 57 ms 64008 KB Output is correct
29 Correct 74 ms 64096 KB Output is correct
30 Correct 59 ms 63860 KB Output is correct
31 Correct 66 ms 64068 KB Output is correct
32 Correct 53 ms 64140 KB Output is correct
33 Correct 65 ms 64044 KB Output is correct
34 Correct 72 ms 63820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 30 ms 62948 KB Output is correct
4 Correct 35 ms 62948 KB Output is correct
5 Correct 29 ms 62936 KB Output is correct
6 Correct 31 ms 62892 KB Output is correct
7 Correct 33 ms 62856 KB Output is correct
8 Correct 31 ms 62940 KB Output is correct
9 Correct 30 ms 62940 KB Output is correct
10 Correct 30 ms 62920 KB Output is correct
11 Correct 31 ms 62920 KB Output is correct
12 Correct 30 ms 62928 KB Output is correct
13 Correct 31 ms 62888 KB Output is correct
14 Correct 31 ms 62896 KB Output is correct
15 Correct 31 ms 62840 KB Output is correct
16 Correct 31 ms 62904 KB Output is correct
17 Correct 38 ms 62888 KB Output is correct
18 Correct 29 ms 62824 KB Output is correct
19 Correct 30 ms 62844 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 37 ms 62932 KB Output is correct
22 Correct 29 ms 62932 KB Output is correct
23 Correct 29 ms 62844 KB Output is correct
24 Correct 29 ms 62832 KB Output is correct
25 Correct 31 ms 62896 KB Output is correct
26 Correct 30 ms 62880 KB Output is correct
27 Correct 73 ms 64200 KB Output is correct
28 Correct 57 ms 64008 KB Output is correct
29 Correct 74 ms 64096 KB Output is correct
30 Correct 59 ms 63860 KB Output is correct
31 Correct 66 ms 64068 KB Output is correct
32 Correct 53 ms 64140 KB Output is correct
33 Correct 65 ms 64044 KB Output is correct
34 Correct 72 ms 63820 KB Output is correct
35 Correct 134 ms 64320 KB Output is correct
36 Correct 125 ms 64320 KB Output is correct
37 Correct 130 ms 64300 KB Output is correct
38 Correct 132 ms 64296 KB Output is correct
39 Correct 127 ms 64320 KB Output is correct
40 Correct 117 ms 64332 KB Output is correct
41 Correct 116 ms 64396 KB Output is correct
42 Correct 119 ms 64364 KB Output is correct
43 Correct 125 ms 64388 KB Output is correct
44 Correct 118 ms 64328 KB Output is correct
45 Correct 123 ms 64388 KB Output is correct
46 Correct 123 ms 64344 KB Output is correct
47 Correct 119 ms 64368 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 30 ms 62948 KB Output is correct
4 Correct 35 ms 62948 KB Output is correct
5 Correct 29 ms 62936 KB Output is correct
6 Correct 31 ms 62892 KB Output is correct
7 Correct 33 ms 62856 KB Output is correct
8 Correct 31 ms 62940 KB Output is correct
9 Correct 30 ms 62940 KB Output is correct
10 Correct 30 ms 62920 KB Output is correct
11 Correct 31 ms 62920 KB Output is correct
12 Correct 30 ms 62928 KB Output is correct
13 Correct 31 ms 62888 KB Output is correct
14 Correct 31 ms 62896 KB Output is correct
15 Correct 31 ms 62840 KB Output is correct
16 Correct 31 ms 62904 KB Output is correct
17 Correct 38 ms 62888 KB Output is correct
18 Correct 29 ms 62824 KB Output is correct
19 Correct 30 ms 62844 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 37 ms 62932 KB Output is correct
22 Correct 29 ms 62932 KB Output is correct
23 Correct 29 ms 62844 KB Output is correct
24 Correct 29 ms 62832 KB Output is correct
25 Correct 31 ms 62896 KB Output is correct
26 Correct 30 ms 62880 KB Output is correct
27 Correct 73 ms 64200 KB Output is correct
28 Correct 57 ms 64008 KB Output is correct
29 Correct 74 ms 64096 KB Output is correct
30 Correct 59 ms 63860 KB Output is correct
31 Correct 66 ms 64068 KB Output is correct
32 Correct 53 ms 64140 KB Output is correct
33 Correct 65 ms 64044 KB Output is correct
34 Correct 72 ms 63820 KB Output is correct
35 Correct 134 ms 64320 KB Output is correct
36 Correct 125 ms 64320 KB Output is correct
37 Correct 130 ms 64300 KB Output is correct
38 Correct 132 ms 64296 KB Output is correct
39 Correct 127 ms 64320 KB Output is correct
40 Correct 117 ms 64332 KB Output is correct
41 Correct 116 ms 64396 KB Output is correct
42 Correct 119 ms 64364 KB Output is correct
43 Correct 125 ms 64388 KB Output is correct
44 Correct 118 ms 64328 KB Output is correct
45 Correct 123 ms 64388 KB Output is correct
46 Correct 123 ms 64344 KB Output is correct
47 Correct 119 ms 64368 KB Output is correct
48 Correct 1261 ms 78196 KB Output is correct
49 Correct 1266 ms 78184 KB Output is correct
50 Correct 1286 ms 78216 KB Output is correct
51 Correct 1217 ms 77736 KB Output is correct
52 Correct 1220 ms 76460 KB Output is correct
53 Correct 1126 ms 77412 KB Output is correct
54 Correct 1113 ms 76360 KB Output is correct
55 Correct 1140 ms 76188 KB Output is correct
56 Correct 1109 ms 75896 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 30 ms 62948 KB Output is correct
4 Correct 35 ms 62948 KB Output is correct
5 Correct 29 ms 62936 KB Output is correct
6 Correct 31 ms 62892 KB Output is correct
7 Correct 33 ms 62856 KB Output is correct
8 Correct 31 ms 62940 KB Output is correct
9 Correct 30 ms 62940 KB Output is correct
10 Correct 30 ms 62920 KB Output is correct
11 Correct 31 ms 62920 KB Output is correct
12 Correct 30 ms 62928 KB Output is correct
13 Correct 31 ms 62888 KB Output is correct
14 Correct 31 ms 62896 KB Output is correct
15 Correct 31 ms 62840 KB Output is correct
16 Correct 31 ms 62904 KB Output is correct
17 Correct 38 ms 62888 KB Output is correct
18 Correct 29 ms 62824 KB Output is correct
19 Correct 30 ms 62844 KB Output is correct
20 Correct 31 ms 62924 KB Output is correct
21 Correct 37 ms 62932 KB Output is correct
22 Correct 29 ms 62932 KB Output is correct
23 Correct 29 ms 62844 KB Output is correct
24 Correct 29 ms 62832 KB Output is correct
25 Correct 31 ms 62896 KB Output is correct
26 Correct 30 ms 62880 KB Output is correct
27 Correct 73 ms 64200 KB Output is correct
28 Correct 57 ms 64008 KB Output is correct
29 Correct 74 ms 64096 KB Output is correct
30 Correct 59 ms 63860 KB Output is correct
31 Correct 66 ms 64068 KB Output is correct
32 Correct 53 ms 64140 KB Output is correct
33 Correct 65 ms 64044 KB Output is correct
34 Correct 72 ms 63820 KB Output is correct
35 Correct 134 ms 64320 KB Output is correct
36 Correct 125 ms 64320 KB Output is correct
37 Correct 130 ms 64300 KB Output is correct
38 Correct 132 ms 64296 KB Output is correct
39 Correct 127 ms 64320 KB Output is correct
40 Correct 117 ms 64332 KB Output is correct
41 Correct 116 ms 64396 KB Output is correct
42 Correct 119 ms 64364 KB Output is correct
43 Correct 125 ms 64388 KB Output is correct
44 Correct 118 ms 64328 KB Output is correct
45 Correct 123 ms 64388 KB Output is correct
46 Correct 123 ms 64344 KB Output is correct
47 Correct 119 ms 64368 KB Output is correct
48 Correct 1261 ms 78196 KB Output is correct
49 Correct 1266 ms 78184 KB Output is correct
50 Correct 1286 ms 78216 KB Output is correct
51 Correct 1217 ms 77736 KB Output is correct
52 Correct 1220 ms 76460 KB Output is correct
53 Correct 1126 ms 77412 KB Output is correct
54 Correct 1113 ms 76360 KB Output is correct
55 Correct 1140 ms 76188 KB Output is correct
56 Correct 1109 ms 75896 KB Output is correct
57 Execution timed out 2540 ms 155664 KB Time limit exceeded
58 Halted 0 ms 0 KB -