Submission #684064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684064	2023-01-20T08:31:50 Z	MilosMilutinovic	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	296 ms	29572 KB

route

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (*min_element(a.begin(), a.end()) == *max_element(a.begin(), a.end())) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> par(n);
  vector<int> L(n);
  vector<int> R(n);
  vector<int> sz(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    L[i] = i;
    R[i] = i;
    sz[i] = 1;
  }
  function<int(int)> Get = [&](int x) {
    return par[x] == x ? x : par[x] = Get(par[x]);
  };
  auto Unite = [&](int x, int y) {
    x = Get(x);
    y = Get(y);
    if (Get((R[y] + 1) % n) == x) {
      swap(x, y);
    }
    sz[x] += sz[y];
    par[y] = x;
    R[x] = R[y];
  };
  for (int i = 0; i < n; i++) {
    if (a[(i + 1) % n] == a[i]) {
      Unite(i, (i + 1) % n);
    }
  }
  auto Valid = [&](int i) {
    i = Get(i);
    int lx = Get((L[i] - 1 + n) % n);
    int rx = Get((R[i] + 1) % n);
    return a[i] < min(a[lx], a[rx]);
  };
  set<pair<int, int>> st;
  for (int i = 0; i < n; i++) {
    if (i == Get(i) && Valid(i)) {
      st.emplace(sz[i], i);
    }
  }
  auto Fix = [&](int x) {
    int lx = Get((L[x] - 1 + n) % n);
    int rx = Get((R[x] + 1) % n);
    int mn = min(a[lx], a[rx]);
    a[x] = mn;
    if (a[lx] == mn) {
      Unite(lx, x);
    }
    if (a[rx] == mn) {
      Unite(rx, x);
    }
    lx = Get(lx);
    rx = Get(rx);
    x = Get(x);
    if (Valid(lx)) {
      st.emplace(sz[lx], lx);
    }
    if (Valid(rx)) {
      st.emplace(sz[rx], rx);
    }
    if (Valid(x)) {
      st.emplace(sz[x], x);
    }
  };
  auto MaxOps = [&](int x) {
    int lx = Get((L[x] - 1 + n) % n);
    int rx = Get((R[x] + 1) % n);
    return min(a[lx], a[rx]) - a[x];
  };
  int ans = 0;
  while (!st.empty()) {
    auto it = st.begin();
    int i = Get(it->second);
    st.erase(it);
    int x = min(k / sz[i], MaxOps(i));
    k -= x * sz[i];
    ans += 2 * x;
    Fix(i);
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	29 ms	3176 KB	Output is correct
11	Correct	62 ms	4808 KB	Output is correct
12	Correct	21 ms	3136 KB	Output is correct
13	Correct	265 ms	29456 KB	Output is correct
14	Correct	280 ms	29572 KB	Output is correct
15	Correct	289 ms	27512 KB	Output is correct
16	Correct	270 ms	28464 KB	Output is correct
17	Correct	287 ms	28388 KB	Output is correct
18	Correct	271 ms	29264 KB	Output is correct
19	Correct	296 ms	29556 KB	Output is correct
20	Correct	180 ms	25728 KB	Output is correct