This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,long long> d[N];
vector<int> vv[N];
vector<int> add[N];
vector<int> del[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
int n = p.size();
int m = l.size();
if(s == 0 && g == n-1){
vector<pair<int,int>> v;
for(int i = 0;i<n;i++){
v.push_back({h[i],i});
adj[i][0].push_back(i);
}
for(int i = 0;i<m;i++){
vv[r[i]].push_back(i);
v.push_back({y[i],~i});
add[r[i]].push_back(i);
del[l[i]].push_back(i);
}
set<pair<int,int>> act;
for(int i = n-1;i>=0;i--){
for(auto u:add[i]){
act.insert({y[u],u});
}
// cout << "asdasd" << endl;
// cout << i << endl;
// for(auto u:act){
// cout << u.first << " " << u.second << endl;
// }
for(auto u:vv[i]){
// cout << u << endl;
auto it = act.lower_bound({y[u],u});
if(next(it) != act.end()){
adj[i][next(it)->first].push_back(r[next(it)->second]);
adj[r[next(it)->second]][next(it)->first].push_back(i);
}
if(it != act.begin()){
adj[i][prev(it)->first].push_back(r[prev(it)->second]);
adj[r[prev(it)->second]][prev(it)->first].push_back(i);
}
}
for(auto u:del[i]){
act.erase({y[u],u});
}
}
sort(v.rbegin(),v.rend());
set<int> active;
for(auto u:v){
if(u.second < 0){
u.second = ~u.second;
auto it = active.lower_bound(max(s,l[u.second]));
auto it2 = active.lower_bound(min(g,r[u.second]));
adj[*it][y[u.second]].push_back(*it2);
adj[*it2][y[u.second]].push_back(*it);
// while(1){
// auto it2 = it;
// it2++;
// if(it2 == active.end() || *it2 > r[u.second])
// break;
// adj[*it][y[u.second]].push_back(*it2);
// adj[*it2][y[u.second]].push_back(*it);
// it = it2;
// }
}
else{
active.insert(u.second);
}
}
priority_queue<pair<long long,pair<int,int>>> q;
d[s][0] = 0;
q.push({-d[s][0],{s,0}});
while(q.size()){
auto tp = q.top();
q.pop();
tp.first *= -1;
int x = tp.second.first;
int y = tp.second.second;
if(tp.first != d[x][y])
continue;
// cout << x << ' ' << y << endl;
// cout << tp.first << endl;
for(auto u:adj[x][y]){
long long nw = abs(p[x] - p[u]) + tp.first;
if(d[u].count(y) == 0 || d[u][y] > nw){
d[u][y] = nw;
q.push({-d[u][y],{u,y}});
}
}
auto it = adj[x].find(y);
if(next(it) != adj[x].end()){
long long nw = abs(y - next(it)->first) + tp.first;
if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
d[x][next(it)->first] = nw;
q.push({-d[x][next(it)->first],{x,next(it)->first}});
}
}
if(it != adj[x].begin()){
long long nw = abs(y - prev(it)->first) + tp.first;
if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
d[x][prev(it)->first] = nw;
q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
}
}
}
return (d[g].count(0)?d[g][0]:-1);
}
vector<pair<int,int>> v;
for(int i = 0;i<n;i++){
v.push_back({h[i],i});
adj[i][0].push_back(i);
}
for(int i = 0;i<m;i++){
v.push_back({y[i],~i});
}
sort(v.rbegin(),v.rend());
set<int> active;
for(auto u:v){
if(u.second < 0){
u.second = ~u.second;
auto it = active.lower_bound(l[u.second]);
while(1){
auto it2 = it;
it2++;
if(it2 == active.end() || *it2 > r[u.second])
break;
adj[*it][y[u.second]].push_back(*it2);
adj[*it2][y[u.second]].push_back(*it);
it = it2;
}
}
else{
active.insert(u.second);
}
}
priority_queue<pair<long long,pair<int,int>>> q;
d[s][0] = 0;
q.push({-d[s][0],{s,0}});
while(q.size()){
auto tp = q.top();
q.pop();
tp.first *= -1;
int x = tp.second.first;
int y = tp.second.second;
if(tp.first != d[x][y])
continue;
// cout << x << ' ' << y << endl;
// cout << tp.first << endl;
for(auto u:adj[x][y]){
long long nw = abs(p[x] - p[u]) + tp.first;
if(d[u].count(y) == 0 || d[u][y] > nw){
d[u][y] = nw;
q.push({-d[u][y],{u,y}});
}
}
auto it = adj[x].find(y);
if(next(it) != adj[x].end()){
long long nw = abs(y - next(it)->first) + tp.first;
if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
d[x][next(it)->first] = nw;
q.push({-d[x][next(it)->first],{x,next(it)->first}});
}
}
if(it != adj[x].begin()){
long long nw = abs(y - prev(it)->first) + tp.first;
if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
d[x][prev(it)->first] = nw;
q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
}
}
}
return (d[g].count(0)?d[g][0]:-1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |