Submission #422801

#	Time	Username	Problem	Language	Result	Execution time	Memory
422801		SSRS	Sky Walking (IOI19_walk)	C++14	57 / 100	4085 ms	494212 KiB

walk

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
struct segment_tree{
  int N;
  vector<long long> ST;
  segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<long long>(N * 2 - 1, INF);
  }
  void update(int i, long long x){
    i += N - 1;
    ST[i] = x;
    while (i > 0){
      i = (i - 1) / 2;
      ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  long long range_min(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return INF;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return min(range_min(L, R, i * 2 + 1, l, m), range_min(L, R, i * 2 + 2, m, r));
    }
  }
  long long range_min(int L, int R){
    return range_min(L, R, 0, 0, N);
  }
};
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
  int n = x.size();
  int m = y.size();
  if (s != 0 || g != n - 1){
    vector<tuple<int, int, int>> T;
    for (int i = 0; i < n; i++){
      T.push_back(make_tuple(h[i], 1, i));
    }
    for (int i = 0; i < m; i++){
      T.push_back(make_tuple(y[i], 0, i));
    }
    sort(T.begin(), T.end(), greater<tuple<int, int, int>>());
    vector<vector<int>> id(m);
    set<int> st;
    for (int i = 0; i < n + m; i++){
      int t = get<1>(T[i]);
      int p = get<2>(T[i]);
      if (t == 0){
        auto itr = st.lower_bound(l[p]);
        while (true){
          id[p].push_back(*itr);
          if (*itr == r[p]){
            break;
          }
          itr++;
        }
      }
      if (t == 1){
        st.insert(p);
      }
    }
    vector<vector<int>> h2(n);
    for (int i = 0; i < n; i++){
      h2[i].push_back(0);
    }
    for (int i = 0; i < m; i++){
      for (int j : id[i]){
        h2[j].push_back(y[i]);
      }
    }
    for (int i = 0; i < n; i++){
      sort(h2[i].begin(), h2[i].end());
      h2[i].erase(unique(h2[i].begin(), h2[i].end()), h2[i].end());
    }
    int V = 0;
    vector<vector<int>> id2(n);
    for (int i = 0; i < n; i++){
      int cnt = h2[i].size();
      id2[i] = vector<int>(cnt);
      for (int j = 0; j < cnt; j++){
        id2[i][j] = V;
        V++;
      }
    }
    vector<vector<pair<int, int>>> E(V);
    for (int i = 0; i < n; i++){
      int cnt = h2[i].size();
      for (int j = 0; j < cnt - 1; j++){
        int v = id2[i][j];
        int w = id2[i][j + 1];
        int d = h2[i][j + 1] - h2[i][j];
        E[v].push_back(make_pair(d, w));
        E[w].push_back(make_pair(d, v));
      }
    }
    for (int i = 0; i < m; i++){
      int cnt = id[i].size();
      vector<int> t(cnt);
      for (int j = 0; j < cnt; j++){
        int p = lower_bound(h2[id[i][j]].begin(), h2[id[i][j]].end(), y[i]) - h2[id[i][j]].begin();
        t[j] = id2[id[i][j]][p];
      }
      for (int j = 0; j < cnt - 1; j++){
        int v = t[j];
        int w = t[j + 1];
        int d = x[id[i][j + 1]] - x[id[i][j]];
        E[v].push_back(make_pair(d, w));
        E[w].push_back(make_pair(d, v));
      }
    }
    int s2 = id2[s][0];
    int g2 = id2[g][0];
    vector<long long> d(V, -1);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push(make_pair(0, s2));
    while (!pq.empty()){
      long long dd = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      if (d[v] == -1){
        d[v] = dd;
        for (auto P : E[v]){
          int w = P.second;
          if (d[w] == -1){
            pq.push(make_pair(dd + P.first, w));
          }
        }
      }
    }
    return d[g2];
  } else {
    vector<pair<int, int>> P(m);
    for (int i = 0; i < m; i++){
      P[i] = make_pair(y[i], i);
    }
    sort(P.begin(), P.end());
    vector<int> pos(m);
    for (int i = 0; i < m; i++){
      pos[i] = lower_bound(P.begin(), P.end(), make_pair(y[i], i)) - P.begin();
    }
    vector<vector<int>> add(n), sub(n);
    for (int i = 0; i < m; i++){
      add[l[i]].push_back(i);
      sub[r[i]].push_back(i);
    }
    segment_tree ST1(m), ST2(m);
    for (int i : add[0]){
      ST1.update(pos[i], y[i] * 2);
      ST2.update(pos[i], 0);
    }
    for (int i = 1; i < n - 1; i++){
      for (int j : add[i]){
        long long mn1 = ST1.range_min(pos[j], m);
        long long mn2 = ST2.range_min(0, pos[j]);
        long long dp = min(mn1 - y[j], mn2 + y[j]);
        ST1.update(pos[j], dp + y[j]);
        ST2.update(pos[j], dp - y[j]);
      }
      for (int j : sub[i]){
        ST1.update(pos[j], INF);
        ST2.update(pos[j], INF);
      }
    }
    long long ans = ST1.range_min(0, m);
    ans += x[n - 1] - x[0];
    if (ans > INF / 2){
      return -1;
    } else {
      return ans;
    }
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43