#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, s, g;
vector<int> x, h, l, r, y;
struct sky {
int lt, rt, val, idx;
} walk[101010];
bool compare(sky a, sky b) {
if (a.rt == b.rt) return a.lt > b.lt;
return a.rt < b.rt;
}
void sort_end() {
for (int i = 0; i < m; i++) walk[i] = {l[i], r[i], y[i]};
sort(walk, walk + m, compare);
for (int i = 0; i < m; i++) {
l[i] = walk[i].lt;
r[i] = walk[i].rt;
y[i] = walk[i].val;
}
}
set<int> xpset, xmset;
vector< pair< pair<int, int>, int > > points;
vector<int> ylist;
vector<int> add[101010], rem[101010];
bool compval(sky a, sky b) {
return a.val < b.val;
}
void get_points() {
for (int i = 0; i < m; i++) ylist.push_back(walk[i].val);
sort(ylist.begin(), ylist.end());
ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
for (int i = 0; i < m; i++) walk[i].idx = i;
sort(walk, walk + m, compval);
for (int i = 0; i < m; i++)
walk[i].val = lower_bound(ylist.begin(), ylist.end(), walk[i].val) - ylist.begin();
for (int i = 0; i < m; i++) add[walk[i].val].push_back(i);
int p = 0;
for (int i = 0; i < m; i++) {
while (p <= walk[i].val) {
for (int j = 0; j < add[p].size(); j++) {
int tar = add[p][j];
xpset.insert(tar);
xmset.insert(-tar);
}
p++;
}
if (walk[i].lt < s && s < walk[i].rt) {
points.push_back({{*xpset.upper_bound(s), ylist[walk[i].val]}, walk[i].idx});
points.push_back({{-*xmset.upper_bound(-s), ylist[walk[i].val]}, walk[i].idx});
}
if (walk[i].lt < g && g < walk[i].rt) {
points.push_back({{*xpset.upper_bound(g), ylist[walk[i].val]}, walk[i].idx});
points.push_back({{-*xmset.upper_bound(-g), ylist[walk[i].val]}, walk[i].idx});
}
points.push_back({{walk[i].lt, ylist[walk[i].val]}, walk[i].idx});
points.push_back({{walk[i].rt, ylist[walk[i].val]}, walk[i].idx});
}
for (int i = 0; i < m; i++) add[i].clear();
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
}
set< pair<int, int> > pset, mset;
vector< pair< pair<int, int>, int > > vertex;
void get_updn() {
for (int i = 0; i < m; i++) add[l[i]].push_back(i);
for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);
int p = 0;
for (int i = 0; i < points.size(); i++) {
int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
while (p <= X) {
for (int j = 0; j < add[p].size(); j++) {
int tar = add[p][j];
pset.insert({y[tar], tar});
mset.insert({-y[tar], tar});
}
for (int j = 0; j < rem[p].size(); j++) {
int tar = rem[p][j];
pset.erase({y[tar], tar});
mset.erase({-y[tar], tar});
}
p++;
}
if (pset.lower_bound({Y, num + 1}) == pset.end());
else vertex.push_back({
{X, pset.lower_bound({Y, num + 1})->first},
pset.lower_bound({Y, num + 1})->second
});
if (mset.lower_bound({-Y, num + 1}) == mset.end());
else vertex.push_back({
{X, -mset.lower_bound({-Y, num + 1})->first},
mset.lower_bound({-Y, num + 1})->second
});
vertex.push_back({{X, Y}, num});
}
for (int i = 0; i < m; i++) add[i].clear();
for (int i = 0; i < m; i++) rem[i].clear();
vertex.push_back({{s, 0}, -1});
vertex.push_back({{g, 0}, -1});
sort(vertex.begin(), vertex.end());
vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}
vector< pair<int, ll> > adj[2020202];
void link_updn() {
for (int i = 0; i < m; i++) add[l[i]].push_back(i);
for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);
int p = 0;
for (int i = 0; i < points.size(); i++) {
int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
while (p <= X) {
for (int j = 0; j < add[p].size(); j++) {
int tar = add[p][j];
pset.insert({y[tar], tar});
mset.insert({-y[tar], tar});
}
for (int j = 0; j < rem[p].size(); j++) {
int tar = rem[p][j];
pset.erase({y[tar], tar});
mset.erase({-y[tar], tar});
}
p++;
}
int now = lower_bound(vertex.begin(), vertex.end(), points[i]) - vertex.begin();
pair< pair<int, int>, int > up, dn;
if (pset.lower_bound({Y, num + 1}) == pset.end());
else {
up = {
{X, pset.lower_bound({Y, num + 1})->first},
pset.lower_bound({Y, num + 1})->second
};
adj[now].push_back({
lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin(),
pset.lower_bound({Y, num + 1})->first - points[i].first.second
});
adj[lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin()].push_back({
now,
pset.lower_bound({Y, num + 1})->first - points[i].first.second
});
}
if (mset.lower_bound({-Y, num + 1}) == mset.end());
else {
dn = {
{X, -mset.lower_bound({-Y, num + 1})->first},
mset.lower_bound({-Y, num + 1})->second
};
adj[now].push_back({
lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin(),
points[i].first.second + mset.lower_bound({-Y, num + 1})->first
});
adj[lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin()].push_back({
now,
points[i].first.second + mset.lower_bound({-Y, num + 1})->first
});
}
}
for (int i = 0; i < m; i++) add[i].clear();
for (int i = 0; i < m; i++) rem[i].clear();
}
vector<int> xlist[101010];
void link_walk() {
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].second >= 0) xlist[vertex[i].second].push_back(vertex[i].first.first);
}
for (int i = 0; i < m; i++) sort(xlist[i].begin(), xlist[i].end());
for (int i = 0; i < m; i++) {
for (int j = 1; j < xlist[i].size(); j++) {
int lt = lower_bound(vertex.begin(), vertex.end(), make_pair(
make_pair(xlist[i][j - 1], y[i]), i
)) - vertex.begin();
int rt = lower_bound(vertex.begin(), vertex.end(), make_pair(
make_pair(xlist[i][j], y[i]), i
)) - vertex.begin();
adj[lt].push_back({rt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
adj[rt].push_back({lt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
}
}
}
void link_sted() {
int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].first.first == 0) {
adj[i].push_back({st, vertex[i].first.second});
adj[st].push_back({i, vertex[i].first.second});
}
}
int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
for (int i = 0; i < vertex.size(); i++) {
if (vertex[i].first.first == n - 1) {
adj[i].push_back({ed, vertex[i].first.second});
adj[ed].push_back({i, vertex[i].first.second});
}
}
}
ll dis[2020202];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
for (int i = 0; i <= 2000000; i++) dis[i] = 1e18;
int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
dis[st] = 0;
pq.push({-dis[st], st});
while (!pq.empty()) {
int now = pq.top().second; ll nowdis = -pq.top().first;
pq.pop();
for (int i = 0; i < adj[now].size(); i++) {
int next = adj[now][i].first;
if (dis[next] > nowdis + adj[now][i].second) {
dis[next] = nowdis + adj[now][i].second;
pq.push({-dis[next], next});
}
}
}
}
ll 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) {
x = X; h = H; l = L; r = R; y = Y; s = S; g = G;
n = x.size();
m = l.size();
sort_end();
get_points();
get_updn();
link_updn();
link_walk();
link_sted();
dijkstra();
int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
ll ans = dis[ed];
if (ans >= 1e18) return -1;
return ans;
}
Compilation message
walk.cpp: In function 'void get_points()':
walk.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void get_updn()':
walk.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j = 0; j < rem[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < points.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int j = 0; j < add[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int j = 0; j < rem[p].size(); j++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:182:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for (int j = 1; j < xlist[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp:205:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | for (int i = 0; i < vertex.size(); i++) {
| ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:223:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for (int i = 0; i < adj[now].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
70460 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70504 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
70452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
70440 KB |
Output is correct |
| 2 |
Correct |
28 ms |
70476 KB |
Output is correct |
| 3 |
Incorrect |
712 ms |
140256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
100052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
100052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
70460 KB |
Output is correct |
| 2 |
Correct |
29 ms |
70504 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
70452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
