Submission #422770

#	Time	Username	Problem	Language	Result	Execution time	Memory
422770		SSRS	Sky Walking (IOI19_walk)	C++14	0 / 100	71 ms	5568 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();
  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();
  }
  segment_tree ST1(m), ST2(m);
  for (int i = 0; i < m; i++){
    if (l[i] == 0){
      ST1.update(pos[i], y[i] * 2);
      ST2.update(pos[i], 0);
    }
  }
  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);
  }
  for (int i = 1; i < n; i++){
    for (int j : add[i]){
      int r = lower_bound(P.begin(), P.end(), make_pair(h[i] + 1, 0)) - P.begin();
      long long mn1 = ST1.range_min(pos[j], r);
      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]);
    }
    if (i < n - 1){
      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];
  if (ans > INF / 2){
    return -1;
  } else {
    return ans;
  }
}

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