Submission #782336

#	Time	Username	Problem	Language	Result	Execution time	Memory
782336		ikaurov	Ancient Books (IOI17_books)	C++17	100 / 100	614 ms	102604 KiB

books

// #include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int N = 1e6 + 20, INF = 1e9;

int t[4 * N];

void modify(int v, int tl, int tr, int pos, int val){
  if (tl == tr){
    t[v] = val;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) modify(2 * v + 1, tl, tm, pos, val);
  else modify(2 * v + 2, tm + 1, tr, pos, val);
  t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

int query(int v, int tl, int tr, int l, int r){
  if (l > r) return INF;
  if (tl == l && tr == r) return t[v];
  int tm = (tl + tr) / 2;
  return min(
    query(2 * v + 1, tl, tm, l, min(r, tm)),
    query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r)
  );
}

long long minimum_walk(std::vector<int> p, int s) {
	int n = sz(p);
  ll ans = 0;
  for (int i = 0; i < n; i++){
    ans += abs(i - p[i]);
  }
  int mincycle = -1, maxcycle = -1;
  for (int i = 0; i < n; i++) if (i != p[i]){
    mincycle = i;
    break;
  }
  for (int i = n - 1; i >= 0; i--) if (i != p[i]){
    maxcycle = i;
    break;
  }
  if (mincycle == -1) return 0;
  for (int i = mincycle, mx = -1; i < n;){
    mx = max(mx, p[i]);
    if (mx <= i){
      int j = i + 1;
      while (j < n && j == p[j]) j++;
      if (j == n) break;
      ans += 2 * (j - i), i = j;
    }
    else i++;
  }
  if (s < mincycle) return ans + 2 * (mincycle - s);
  if (s > maxcycle) return ans + 2 * (s - maxcycle);
  vector<bool> cycleend(n);
  for (int i = 0, mx = -1; i < n; i++){
    mx = max(mx, p[i]);
    if (mx <= i) cycleend[i] = 1;
  }

  vector<int> cur, used(n), cid(n), minpos(n, INF), maxpos(n, -1);
  vector<int> minl(n, INF), maxr(n, -1);
  vector<vector<int>> has(n);

  int id = 0;

  function<void(int)> dfs = [&] (int v){
    used[v] = 1, cid[v] = id;
    minpos[id] = min(minpos[id], v);
    maxpos[id] = max(maxpos[id], v);
    has[id].pb(v);
    if (!used[p[v]]) dfs(p[v]);
  };

  for (int i = 0; i < n; i++){
    if (used[i]) continue;
    dfs(i);
    id++;
  }

  vector<int> order(id);
  iota(all(order), 0);

  sort(all(order), [&] (int i, int j){
    return minpos[i] < minpos[j];
  });

  for (int i = 0; i < 4 * n; i++) t[i] = INF;

  for (auto i : order){
    minl[i] = min(minpos[i], query(0, 0, n - 1, minpos[i], maxpos[i]));
    for (auto v : has[i]) modify(0, 0, n - 1, v, minl[i]);
  }

  sort(all(order), [&] (int i, int j){
    return maxpos[i] > maxpos[j];
  });

  for (int i = 0; i < 4 * n; i++) t[i] = INF;

  for (auto i : order){
    maxr[i] = max(maxpos[i], -query(0, 0, n - 1, minpos[i], maxpos[i]));
    for (auto v : has[i]) modify(0, 0, n - 1, v, -maxr[i]);
  }

  int startl = s, startr = s;
  while (startl > 0 && !cycleend[startl - 1]) startl--;
  while (!cycleend[startr]) startr++;

  vector<int> ids;

  for (int i = 0; i < id; i++) if (minl[i] <= s && maxr[i] >= maxr[cid[s]]) ids.pb(i);

  sort(all(ids), [&] (int i, int j){
    return maxr[i] < maxr[j];
  });

  ll ans1 = 0;

  for (int i = 1; i < sz(ids); i++){
    int l = minl[ids[i - 1]], cur1 = 0;
    while (l > minl[ids[i]]) l--, l = minl[cid[l]], cur1++;

    int r = maxr[ids[i - 1]], cur2 = 0;
    while (r < maxr[ids[i]]) r++, r = maxr[cid[r]], cur2++;

    ans1 += min(cur1, cur2);
  }

  return ans + 2 * ans1;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30