oj.uz

Submission #289883

# Submission time Handle Problem Language Result Execution time Memory
289883 2020-09-03T07:52:59 Z rama_pang Railway Trip (JOI17_railway_trip) C++14
45 / 100
 2000 ms 73276 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(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);
      }
      int between = Between(parent[a].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].first != Name(-1, N)) {
        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({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 i = 0; i < Q; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    cout << Query(a, b, i == 3) - 1 << '\n';
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 45560 KB Output is correct
2 Correct 31 ms 45440 KB Output is correct
3 Correct 34 ms 45432 KB Output is correct
4 Correct 39 ms 45432 KB Output is correct
5 Correct 39 ms 45432 KB Output is correct
6 Correct 40 ms 45432 KB Output is correct
7 Correct 35 ms 45408 KB Output is correct
8 Correct 31 ms 45440 KB Output is correct
9 Correct 33 ms 45432 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45608 KB Output is correct
2 Correct 245 ms 67104 KB Output is correct
3 Correct 278 ms 68232 KB Output is correct
4 Correct 305 ms 68984 KB Output is correct
5 Correct 263 ms 69512 KB Output is correct
6 Correct 328 ms 70080 KB Output is correct
7 Correct 412 ms 71848 KB Output is correct
8 Correct 162 ms 59708 KB Output is correct
9 Correct 250 ms 71184 KB Output is correct
10 Correct 239 ms 66584 KB Output is correct
11 Correct 250 ms 67776 KB Output is correct
12 Correct 249 ms 67580 KB Output is correct
13 Correct 234 ms 67508 KB Output is correct
14 Correct 244 ms 67832 KB Output is correct
15 Correct 238 ms 67588 KB Output is correct
16 Correct 235 ms 67444 KB Output is correct
17 Correct 257 ms 70400 KB Output is correct
18 Correct 253 ms 70264 KB Output is correct
19 Correct 271 ms 72824 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 69324 KB Output is correct
2 Correct 498 ms 68772 KB Output is correct
3 Correct 502 ms 69524 KB Output is correct
4 Correct 504 ms 69512 KB Output is correct
5 Correct 502 ms 69760 KB Output is correct
6 Correct 511 ms 69844 KB Output is correct
7 Correct 511 ms 69864 KB Output is correct
8 Correct 406 ms 64132 KB Output is correct
9 Correct 404 ms 61496 KB Output is correct
10 Correct 412 ms 61428 KB Output is correct
11 Correct 399 ms 61424 KB Output is correct
12 Correct 433 ms 61396 KB Output is correct
13 Correct 446 ms 61484 KB Output is correct
14 Correct 498 ms 61432 KB Output is correct
15 Correct 517 ms 61748 KB Output is correct
16 Correct 515 ms 63604 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 73276 KB Output is correct
2 Correct 733 ms 73260 KB Output is correct
3 Correct 756 ms 71888 KB Output is correct
4 Correct 814 ms 72248 KB Output is correct
5 Correct 407 ms 61424 KB Output is correct
6 Execution timed out 2066 ms 71616 KB Time limit exceeded
7 Halted 0 ms 0 KB -