Submission #138241

#	Time	Username	Problem	Language	Result	Execution time	Memory
138241		MAMBA	Ancient Books (IOI17_books)	C++17	100 / 100	1680 ms	121936 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

inline bool smin(int &a, int b) { return b < a ? a = b, true : false; }
inline bool smax(int &a, int b) { return a < b ? a = b, true : false; }

const int N = 1e6 + 10;

int A[N], B[N], n;

int A_[N << 1], B_[N << 1];
#define lid i << 1
#define rid lid | 1

inline int getMin(int l, int r) {
  int res = l;
  for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
    if (l & 1) smin(res, B_[l++]);
    if (r & 1) smin(res, B_[--r]);
  }
  return res;
}
inline int getMax(int l, int r) {
  int res = r;
  for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
    if (l & 1) smax(res, A_[l++]);
    if (r & 1) smax(res, A_[--r]);
  }
  return res;
}

inline void build() {
  rep(i, 0, n) {
    A_[i + n] = A[i];
    B_[i + n] = B[i];
  }
  for (int i = n - 1; i; i--) {
    A_[i] = max(A_[lid], A_[rid]);
    B_[i] = min(B_[lid], B_[rid]);
  }
}

map<pii, pii> mp;

pii extend(int l, int r) {
  if (mp.count({l, r})) return mp[{l, r}];
  int newL = getMin(l, r);
  int newR = getMax(l, r);
  if (newL < l || r < newR) return mp[{l, r}] = extend(newL, newR);
  return mp[{l, r}] = {l, r};
}

ll minimum_walk(vi p, int s) {
  n = p.size();

  fill(A, A + n, -1);
  fill(B, B + n, n);

  ll res = 0;
  int l2 = s, r2 = s;

  rep(i, 0, n) {
    res += abs(i - p[i]);
    int a = min(i, p[i]);
    int b = i ^ p[i] ^ a;
    A[a] = b;
    B[b] = a;
    if (a != b) {
      smin(l2, a);
      smax(r2, b);
    }
  }

  build();

  int l = s, r = s;
  tie(l, r) = extend(l, r);

  while (l != l2 && r != r2) {
    int l0 = l, r0 = r, l1 = l, r1 = r, aa = 0, bb = 0;
    while (true) {
      int lp = l0, rp = r0;
      tie(l0, r0) = extend(l0 - 1, r0);
      aa += 2;
      if (rp != r0 || l0 == l2) break;
    }
    while (true) {
      int lp = l1, rp = r1;
      tie(l1, r1) = extend(l1, r1 + 1);
      bb += 2;
      if (lp != l1 || r1 == r2) break;
    }

    if (r0 == r || l1 == l) {
      res += aa + bb;
      l = l2, r = r2;
      break;
    }
    res += min(aa, bb);
    l = l0, r = r0;
  }
  while (l != l2) {
    res += 2;
    tie(l, r) = extend(l - 1, r);
  }
  while (r != r2) {
    res += 2;
    tie(l, r) = extend(l, r + 1);
  }

  return res;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(vi, int)':
books.cpp:91:11: warning: unused variable 'lp' [-Wunused-variable]
       int lp = l0, rp = r0;
           ^~
books.cpp:97:20: warning: unused variable 'rp' [-Wunused-variable]
       int lp = l1, rp = r1;
                    ^~

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