#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// TODO Watch out for the size
const int MAX_N = 400010 * 10;
const ll inf = 1ll << 55;
#include "walk.h"
// graph is 0 based
int n, m;
vector<int> xup[MAX_N];
vector<int> x, h, pfsz;
vector<pair<int,int>> edge[MAX_N];
int get_id(int i, int j) {
assert(binary_search(AI(xup[i]), j));
return lower_bound(AI(xup[i]), j) - begin(xup[i]) + pfsz[i];
}
void init_ver(std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
for (int i = 0;i < m;++i) {
for (int j = l[i];j <= r[i];++j) {
if (h[j] < y[i]) continue;
xup[j].pb(y[i]);
}
}
for (int i = 0;i < n;++i) {
sort(AI(xup[i]));
xup[i].erase(unique(AI(xup[i])), end(xup[i]));
if (xup[i].size() < 4) continue;
int a = end(xup[i])[-1], b = end(xup[i])[-2];
xup[i].resize(2);
xup[i].pb(a), xup[i].pb(b);
}
xup[s].pb(0), xup[g].pb(0);
for (int i = 0;i < m;++i) {
xup[ l[i] ].pb( y[i] );
xup[ r[i] ].pb( y[i] );
}
pfsz.resize(n+1);
for (int i = 0;i < n;++i) {
sort(AI(xup[i]));
xup[i].erase(unique(AI(xup[i])), end(xup[i]));
pfsz[i+1] = pfsz[i] + xup[i].size();
for (int j = 1;j < xup[i].size();++j) {
int a = pfsz[i]+j-1, b = pfsz[i] + j
//int a = get_id(i, xup[i][j-1]), b = get_id(i, xup[i][j]),
, d = xup[i][j] - xup[i][j-1];
edge[a].pb(b, d);
edge[b].pb(a, d);
}
}
}
void mbuild(vector<int> l, vector<int> r, vector<int> y) {
map<int, vector<int>> xs;
for (int i = 0;i < n;++i) {
for (int j : xup[i])
xs[j].pb(i);
}
for (int i = 0;i < m;++i) {
vector< int > loc;
auto it = lower_bound(AI( xs[y[i]] ), l[i]);
while (it != end(xs[y[i]])) {
if (*it > r[i]) break;
loc.pb(*it++);
}
for (int j = 1;j < loc.size();++j) {
int a = get_id(loc[j-1], y[i]), b = get_id(loc[j], y[i]),
d = x[ loc[j] ] - x[ loc[j-1] ];
edge[a].pb(b, d);
edge[b].pb(a, d);
}
}
}
ll sho(int s, int t) {
int V = pfsz.back() + 10;
vector<ll> dis(V, inf);
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
auto upd = [&](int id, ll d) {
if (chmin(dis[id], d))
pq.emplace(d, id);
};
upd(s, 0);
while (pq.size()) {
auto [d, x] = pq.top(); pq.pop();
if (d != dis[x]) continue;
if (x == t) return d;
DE(x, d);
for (auto [u, w] : edge[x])
upd(u, d + w);
}
return -1;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
n = x.size();
m = l.size();
::x = x;
::h = h;
init_ver(l, r, y, s, g);
mbuild(l, r, y);
return sho( get_id(s, 0), get_id(g, 0) );
}
Compilation message
walk.cpp: In function 'void init_ver(std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int j = 1;j < xup[i].size();++j) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void mbuild(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int j = 1;j < loc.size();++j) {
| ~~^~~~~~~~~~~~
walk.cpp: In function 'll sho(int, int)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
walk.cpp:119:3: note: in expansion of macro 'DE'
119 | DE(x, d);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
188084 KB |
Output is correct |
| 2 |
Correct |
101 ms |
188096 KB |
Output is correct |
| 3 |
Correct |
103 ms |
188040 KB |
Output is correct |
| 4 |
Correct |
102 ms |
188100 KB |
Output is correct |
| 5 |
Correct |
104 ms |
188196 KB |
Output is correct |
| 6 |
Incorrect |
100 ms |
188076 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
188100 KB |
Output is correct |
| 2 |
Correct |
100 ms |
188100 KB |
Output is correct |
| 3 |
Incorrect |
570 ms |
220752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
195072 KB |
Output is correct |
| 2 |
Incorrect |
884 ms |
241772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
195072 KB |
Output is correct |
| 2 |
Incorrect |
884 ms |
241772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
188084 KB |
Output is correct |
| 2 |
Correct |
101 ms |
188096 KB |
Output is correct |
| 3 |
Correct |
103 ms |
188040 KB |
Output is correct |
| 4 |
Correct |
102 ms |
188100 KB |
Output is correct |
| 5 |
Correct |
104 ms |
188196 KB |
Output is correct |
| 6 |
Incorrect |
100 ms |
188076 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
