oj.uz

Submission #289889

# Submission time Handle Problem Language Result Execution time Memory
289889 2020-09-03T08:03:48 Z rama_pang Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1076 ms 273016 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 231264 KB Output is correct
2 Correct 145 ms 231264 KB Output is correct
3 Correct 142 ms 231252 KB Output is correct
4 Correct 154 ms 231288 KB Output is correct
5 Correct 185 ms 231296 KB Output is correct
6 Correct 142 ms 231288 KB Output is correct
7 Correct 137 ms 231288 KB Output is correct
8 Correct 152 ms 231288 KB Output is correct
9 Correct 149 ms 231276 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 231544 KB Output is correct
2 Correct 433 ms 252880 KB Output is correct
3 Correct 478 ms 254120 KB Output is correct
4 Correct 496 ms 254972 KB Output is correct
5 Correct 512 ms 255364 KB Output is correct
6 Correct 523 ms 255864 KB Output is correct
7 Correct 562 ms 257460 KB Output is correct
8 Correct 318 ms 245564 KB Output is correct
9 Correct 390 ms 256936 KB Output is correct
10 Correct 378 ms 252276 KB Output is correct
11 Correct 415 ms 253320 KB Output is correct
12 Correct 426 ms 253220 KB Output is correct
13 Correct 447 ms 253040 KB Output is correct
14 Correct 413 ms 253432 KB Output is correct
15 Correct 448 ms 253268 KB Output is correct
16 Correct 427 ms 253132 KB Output is correct
17 Correct 454 ms 255912 KB Output is correct
18 Correct 466 ms 255900 KB Output is correct
19 Correct 487 ms 258516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 253816 KB Output is correct
2 Correct 816 ms 253576 KB Output is correct
3 Correct 778 ms 254116 KB Output is correct
4 Correct 811 ms 254300 KB Output is correct
5 Correct 806 ms 254364 KB Output is correct
6 Correct 769 ms 254564 KB Output is correct
7 Correct 765 ms 254608 KB Output is correct
8 Correct 667 ms 248880 KB Output is correct
9 Correct 646 ms 246332 KB Output is correct
10 Correct 636 ms 246416 KB Output is correct
11 Correct 663 ms 246236 KB Output is correct
12 Correct 700 ms 246312 KB Output is correct
13 Correct 660 ms 246236 KB Output is correct
14 Correct 573 ms 246360 KB Output is correct
15 Correct 528 ms 246548 KB Output is correct
16 Correct 649 ms 248396 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 257560 KB Output is correct
2 Correct 832 ms 257456 KB Output is correct
3 Correct 866 ms 256376 KB Output is correct
4 Correct 873 ms 256888 KB Output is correct
5 Correct 646 ms 246300 KB Output is correct
6 Correct 850 ms 258192 KB Output is correct
7 Correct 852 ms 258828 KB Output is correct
8 Correct 804 ms 254268 KB Output is correct
9 Correct 783 ms 255420 KB Output is correct
10 Correct 802 ms 255236 KB Output is correct
11 Correct 817 ms 255024 KB Output is correct
12 Correct 779 ms 255436 KB Output is correct
13 Correct 875 ms 255272 KB Output is correct
14 Correct 969 ms 264032 KB Output is correct
15 Correct 992 ms 267460 KB Output is correct
16 Correct 1076 ms 273016 KB Output is correct
17 Correct 980 ms 258784 KB Output is correct
18 Correct 990 ms 259556 KB Output is correct
19 Correct 1018 ms 259644 KB Output is correct
20 Correct 940 ms 255072 KB Output is correct
21 Correct 723 ms 257656 KB Output is correct
22 Correct 828 ms 257620 KB Output is correct
23 Correct 823 ms 260344 KB Output is correct