oj.uz

Submission #289873

# Submission time Handle Problem Language Result Execution time Memory
289873 2020-09-03T07:43:49 Z rama_pang Railway Trip (JOI17_railway_trip) C++14
5 / 100
 646 ms 73328 KB 
#include <bits/stdc++.h>
using namespace std;

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

class Matrix {
 public:
  array<array<int, 2>, 2> M;
  Matrix() {}
  Matrix(int v) {
    M[0][0] = M[0][1] = M[1][0] = M[1][1] = v;
  }
  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];
vector<int> adj[MAXN];
int st[MAXN], et[MAXN];
map<pair<int, int>, int> name;
pair<int, Matrix> parent[MAXN];
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].first = id;
    parent[child].second[0][0] = tmp[2][0];
    parent[child].second[0][1] = tmp[2][1];
    parent[child].second[1][0] = tmp[3][0];
    parent[child].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;
      while (parent[a].first != parent[b].first) {
        if (depth[a] > depth[b]) {
          swap(a, b);
          swap(ca, cb);
        }
        cb = cb * parent[b].second;
        b = parent[b].first;
      }
      if (st[a] > st[b]) {
        swap(a, b);
        swap(ca, cb);
      }
      res = min(res, min(ca[0][1], ca[1][1]) + min(cb[0][0], cb[1][0]) + 
                         Between(parent[a].first, et[a], st[b]));
      ca = ca * parent[a].second;
      cb = cb * parent[b].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)].first = -1;
  parent[Name(-1, N)].second = Matrix(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 i = 0; i < Q; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    cout << Query(a, b) - 1 << '\n';
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 45348 KB Output is correct
2 Correct 30 ms 45468 KB Output is correct
3 Correct 29 ms 45432 KB Output is correct
4 Correct 30 ms 45364 KB Output is correct
5 Correct 29 ms 45432 KB Output is correct
6 Correct 28 ms 45432 KB Output is correct
7 Correct 31 ms 45440 KB Output is correct
8 Correct 28 ms 45408 KB Output is correct
9 Correct 30 ms 45440 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 45704 KB Output is correct
2 Incorrect 242 ms 67100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 466 ms 69320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 73320 KB Output is correct
2 Correct 646 ms 73328 KB Output is correct
3 Incorrect 591 ms 71932 KB Output isn't correct
4 Halted 0 ms 0 KB -