#include "bits/stdc++.h"
using namespace std;
#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
const ll inf = 2e18;
const int N = 1e5 + 5;
struct ST{
vector<ll> tree;
vector<ar<int, 2>> c;
int last;
void add(){
tree.push_back(inf);
c.push_back({});
last++;
}
ST(){ add(); }
void umin(int i, ll v, int lx = 0, int rx = N, int x = 0){
if(lx == rx) {
tree[x] = min(tree[x], v);
return;
} int m = (lx + rx) >> 1;
if(i <= m){
if(!c[x][0]) c[x][0] = last, add();
umin(i, v, lx, m, c[x][0]);
} else {
if(!c[x][1]) c[x][1] = last, add();
umin(i, v, m + 1, rx, c[x][1]);
}
tree[x] = inf;
if(c[x][0]) tree[x] = min(tree[x], tree[c[x][0]]);
if(c[x][1]) tree[x] = min(tree[x], tree[c[x][1]]);
}
ll get(int l, int r, int lx = 0, int rx = N, int x = 0){
if(lx > r || rx < l) return inf;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
ll res = inf;
if(c[x][0]) res = min(res, get(l, r, lx, m, c[x][0]));
if(c[x][1]) res = min(res, get(l, r, m + 1, rx, c[x][1]));
return res;
}
};
struct ST2{
ST tree[N << 2];
void umin(int i, int j, ll v, int lx = 0, int rx = N, int x = 1){
tree[x].umin(j, v);
if(lx == rx) return;
int m = (lx + rx) >> 1;
if(i <= m) umin(i, j, v, lx, m, x << 1);
else umin(i, j, v, m + 1, rx, x << 1 | 1);
}
ll get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return inf;
if(lx >= l && rx <= r){
return tree[x].get(l_, r_);
}
int m = (lx + rx) >> 1;
return min(get(l, r, l_, r_, lx, m, x << 1), get(l, r, l_, r_, m + 1, rx, x << 1 | 1));
}
}add, sub;
vector<ar<int, 2>> edges[N * 11];
ll d[N * 11];
#define sow cout<<"here"<<endl;
ll 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(), q = l.size();
vector<int> p(q); iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return r[i] < r[j];
});
vector<int> tot;
vector<ll> dp(q, inf);
for(int i=0;i<q;i++){
tot.push_back(y[i]);
}
sort(tot.begin(), tot.end());
tot.erase(unique(tot.begin(), tot.end()), tot.end());
ll res = inf;
sub.umin(0, 0, 0);
add.umin(0, 0, 0);
for(auto i : p){
if(y[i] > h[0]) continue;
int j = lower_bound(tot.begin(), tot.end(), y[i]) - tot.begin() + 1;
dp[i] = min(dp[i], sub.get(l[i], r[i], 0, j) + y[i]);
dp[i] = min(dp[i], add.get(l[i], r[i], j, q) - y[i]);
sub.umin(r[i], j, dp[i] - y[i]);
add.umin(r[i], j, dp[i] + y[i]);
if(r[i] == n - 1) res = min(res, dp[i]);
}
res += (x[n - 1] - x[0]);
if(res < 1e18){
return res;
} else {
return -1;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
119996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
120128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
141628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
141628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
119996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
