oj.uz

답안 #422797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422797 2021-06-10T12:33:28 Z SSRS Sky Walking (IOI19_walk) C++14
33 / 100
 263 ms 24488 KB 
#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();
  }
  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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 5624 KB Output is correct
2 Correct 137 ms 9144 KB Output is correct
3 Correct 178 ms 12324 KB Output is correct
4 Correct 244 ms 22172 KB Output is correct
5 Correct 199 ms 20676 KB Output is correct
6 Correct 215 ms 22080 KB Output is correct
7 Correct 130 ms 16196 KB Output is correct
8 Correct 254 ms 24488 KB Output is correct
9 Correct 260 ms 23140 KB Output is correct
10 Correct 166 ms 21268 KB Output is correct
11 Correct 14 ms 4216 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 5624 KB Output is correct
2 Correct 137 ms 9144 KB Output is correct
3 Correct 178 ms 12324 KB Output is correct
4 Correct 244 ms 22172 KB Output is correct
5 Correct 199 ms 20676 KB Output is correct
6 Correct 215 ms 22080 KB Output is correct
7 Correct 130 ms 16196 KB Output is correct
8 Correct 254 ms 24488 KB Output is correct
9 Correct 260 ms 23140 KB Output is correct
10 Correct 166 ms 21268 KB Output is correct
11 Correct 14 ms 4216 KB Output is correct
12 Correct 198 ms 12284 KB Output is correct
13 Correct 229 ms 22084 KB Output is correct
14 Correct 207 ms 20604 KB Output is correct
15 Correct 211 ms 21280 KB Output is correct
16 Correct 202 ms 21456 KB Output is correct
17 Correct 201 ms 21600 KB Output is correct
18 Correct 208 ms 21188 KB Output is correct
19 Correct 246 ms 21444 KB Output is correct
20 Correct 118 ms 15992 KB Output is correct
21 Correct 32 ms 8620 KB Output is correct
22 Correct 168 ms 19832 KB Output is correct
23 Correct 179 ms 20268 KB Output is correct
24 Correct 195 ms 20676 KB Output is correct
25 Correct 180 ms 20140 KB Output is correct
26 Correct 207 ms 21188 KB Output is correct
27 Correct 213 ms 21040 KB Output is correct
28 Correct 248 ms 22192 KB Output is correct
29 Correct 240 ms 22044 KB Output is correct
30 Correct 114 ms 16196 KB Output is correct
31 Correct 250 ms 23104 KB Output is correct
32 Correct 218 ms 20616 KB Output is correct
33 Correct 188 ms 22336 KB Output is correct
34 Correct 168 ms 21440 KB Output is correct
35 Correct 251 ms 21840 KB Output is correct
36 Correct 231 ms 21488 KB Output is correct
37 Correct 216 ms 20096 KB Output is correct
38 Correct 263 ms 23492 KB Output is correct
39 Correct 175 ms 21916 KB Output is correct
40 Correct 246 ms 22364 KB Output is correct
41 Correct 223 ms 20972 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -