Submission #289889

#	Time	Username	Problem	Language	Result	Execution time	Memory
289889		rama_pang	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	1076 ms	273016 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int BITS = 20;
const int INF = 1e8;

class Matrix {
 public:
  array<array<int, 2>, 2> M;
  Matrix() {}
  Matrix(array<array<int, 2>, 2> M) : M(M) {}

  array<int, 2>& operator[](int i) { return M[i]; }
  const array<int, 2>& operator[](int i) const { return M[i]; }
  
  Matrix operator*(const Matrix &o) {
    Matrix res;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        res.M[i][j] = INF;
        for (int k = 0; k < 2; k++) {
          res.M[i][j] = min(res.M[i][j], M[i][k] + o.M[k][j]);
        }
      }
    }
    return res;
  }
};

int N, K, Q;
int level[MAXN];
vector<int> ls[MAXN];

int bigleft[MAXN];
int bigright[MAXN];

int depth[MAXN];
int st[MAXN], et[MAXN];

vector<int> adj[MAXN];
pair<int, Matrix> parent[MAXN][BITS];

map<pair<int, int>, int> name;
vector<pair<int, Matrix>> starter[MAXN];

int Name(int i, int j) {
  if (name.count({i, j})) {
    return name[{i, j}];
  }
  int n = name.size();
  return name[{i, j}] = n;
};

void Build(int l, int r) {
  int id = Name(l, r);
  st[id] = l, et[id] = r;
  if (l + 1 == r) return;
  adj[id].emplace_back(l);
  adj[id].emplace_back(r);
  sort(begin(adj[id]), end(adj[id]));
  for (int i = 0; i + 1 < (int) adj[id].size(); i++) {
    int child = Name(adj[id][i], adj[id][i + 1]);
    depth[child] = depth[id] + 1;
    Build(adj[id][i], adj[id][i + 1]);

    // 0 -- 2 -- 3 -- 1
    array<array<int, 4>, 4> tmp; 
    tmp[0][2] = tmp[2][0] = i;
    tmp[1][3] = tmp[3][1] = int(adj[id].size()) - i - 2;
    tmp[0][3] = tmp[3][0] = i + 1;
    tmp[2][1] = tmp[1][2] = int(adj[id].size()) - i - 1;
    tmp[0][1] = tmp[1][0] = tmp[2][3] = tmp[3][2] = 1;
    tmp[0][0] = tmp[1][1] = tmp[2][2] = tmp[3][3] = 0;
    for (int k = 0; k < 4; k++) {
      for (int n = 0; n < 4; n++) {
        for (int m = 0; m < 4; m++) {
          tmp[n][m] = min(tmp[n][m], tmp[n][k] + tmp[k][m]);
        }
      }
    }
    parent[child][0].first = id;
    parent[child][0].second[0][0] = tmp[2][0];
    parent[child][0].second[0][1] = tmp[2][1];
    parent[child][0].second[1][0] = tmp[3][0];
    parent[child][0].second[1][1] = tmp[3][1];
  }
}

int Query(int a_, int b_, int dbg = 0) {
  if (abs(a_ - b_) == 1) {
    return 1;
  } else if (abs(a_ - b_) == 2) {
    int md = (a_ + b_) / 2;
    if (level[md] >= level[a_] || level[md] >= level[b_]) {
      return 2;
    }
    return 1;
  }
  auto Between = [&](int p, int l, int r) -> int {
    return lower_bound(begin(adj[p]), end(adj[p]), r) - 
           lower_bound(begin(adj[p]), end(adj[p]), l);
  };
  int res = INF;
  for (auto sa : starter[a_]) {
    for (auto sb : starter[b_]) {
      int a = sa.first;
      int b = sb.first;
      auto ca = sa.second;
      auto cb = sb.second;

      if (depth[a] > depth[b]) {
        swap(a, b);
        swap(ca, cb);
      }
      for (int x = 0, diff = depth[b] - depth[a]; x < BITS; x++) {
        if (diff & (1 << x)) {
          cb = cb * parent[b][x].second;
          b = parent[b][x].first;
        }
      }
      for (int x = BITS - 1; x >= 0; x--) {
        if (parent[a][x].first != parent[b][x].first) {
          auto pa = parent[a][x];
          auto pb = parent[b][x];
          if (parent[pa.first][0].first != parent[pb.first][0].first) {
            ca = ca * pa.second;
            cb = cb * pb.second;
            a = pa.first;
            b = pb.first;
          }
        }
      }
      if (parent[a][0].first != parent[b][0].first) {
        ca = ca * parent[a][0].second;
        cb = cb * parent[b][0].second;
        a = parent[a][0].first;
        b = parent[b][0].first;
      }

      if (st[a] > st[b]) swap(a, b), swap(ca, cb);
      assert(parent[a][0].first == parent[b][0].first);
      
      int between = Between(parent[a][0].first, et[a], st[b]);
      res = min(res, min(ca[0][1], ca[1][1]) + min(cb[0][0], cb[1][0]) + between);

      if (parent[a][0].first != Name(-1, N)) {
        ca = ca * parent[a][0].second;
        cb = cb * parent[b][0].second;
        res = min(res, min(ca[0][0], ca[1][0]) + min(cb[0][1], cb[1][1]) + 1);
      }
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> K >> Q;
  for (int i = 0; i < N; i++) {
    cin >> level[i];
    level[i]--;
    ls[level[i]].emplace_back(i);
  }

  vector<int> st;
  for (int i = 0; i < N; i++) {
    while (!st.empty() && level[st.back()] <= level[i]) {
      st.pop_back();
    }
    bigleft[i] = (st.empty() ? -1 : st.back());
    st.emplace_back(i);
  }
  st.clear();
  for (int i = N - 1; i >= 0; i--) {
    while (!st.empty() && level[st.back()] <= level[i]) {
      st.pop_back();
    }
    bigright[i] = (st.empty() ? N : st.back());
    st.emplace_back(i);
  }

  for (int k = 0; k < K; k++) {
    for (auto i : ls[k]) {
      adj[Name(bigleft[i], bigright[i])].emplace_back(i);
    }
  }

  parent[Name(-1, N)][0].first = -1;
  parent[Name(-1, N)][0].second = Matrix({array<int, 2>{INF, INF}, array<int, 2>{INF, INF}});
  Build(-1, N);

  for (int i = 0; i < N; i++) {
    if (i > 0) {
      starter[i].emplace_back(Name(i - 1, i), Matrix({array<int, 2>{1, INF}, array<int, 2>{INF, 0}}));
    }
    if (i + 1 < N) {
      starter[i].emplace_back(Name(i, i + 1), Matrix({array<int, 2>{0, INF}, array<int, 2>{INF, 1}}));
    }
  }

  for (int x = 1; x < BITS; x++) {
    for (int i = 0; i < (int) name.size(); i++) {
      parent[i][x] = parent[i][x - 1];
      if (parent[i][x].first != -1) {
        int p = parent[i][x - 1].first;
        parent[i][x].first = parent[p][x - 1].first;
        parent[i][x].second = parent[i][x - 1].second * parent[p][x - 1].second;
      }
    }
  }

  for (int i = 0; i < Q; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    cout << Query(a, b) - 1 << '\n';
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55