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 ll long long
using namespace std;
const int maxn=2e5+5;
ll N,M;
struct skywalk{
ll l,r,y;
} put[maxn];
struct zgrada{
ll x,y,id;
} niz[maxn];
bool cmpsw(skywalk a,skywalk b){
return a.y<b.y;
}
bool poy(zgrada a,zgrada b){
return a.y<b.y;
}
int gsz=0;
int novi(){
return ++gsz;
}
set<int> S;
vector<pair<int,int>> koji[maxn];
vector<pair<ll,ll>> graf[12*maxn];
bool prosli[12*maxn];
ll dist[12*maxn];
priority_queue<pair<ll,ll>> PQ;
void grana(int a,int b,ll w){
graf[a].push_back({b,w});
graf[b].push_back({a,w});
}
void Dijkstra(ll gde,ll c){
PQ.push({-c,gde});
while(PQ.size()){
ll tren=PQ.top().second;
ll d=-PQ.top().first;
PQ.pop();
if(prosli[tren])
continue;
prosli[tren]=true;
dist[tren]=d;
for(auto x:graf[tren])
PQ.push({-d-x.second,x.first});
}
}
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) {
N=x.size();
M=l.size();
for(ll i=0;i<N;i++){
niz[i].x=x[i];
niz[i].y=h[i];
niz[i].id=i;
}
for(ll i=0;i<M;i++){
put[i].l=l[i];
put[i].r=r[i];
put[i].y=y[i];
}
sort(niz,niz+N,poy);
sort(put,put+M,cmpsw);
ll pok=N-1;
for(ll i=M-1;i>=0;i--){
if(pok>=0){
while(niz[pok].y>=put[i].y){
S.insert(niz[pok].id);
pok--;
if(pok<0)
break;
}
}
vector<ll> V;
auto it=S.upper_bound(put[i].l-1);
for(it;it!=S.end();it++){
if((*it)>put[i].r)
break;
V.push_back(*it);
}
int pn=novi();
koji[V[0]].push_back({put[i].y,pn});
for(ll j=1;j<V.size();j++){
ll pr=V[j-1];
ll tr=V[j];
ll d=x[tr]-x[pr];
int nn=novi();
grana(pn,nn,d);
koji[V[j]].push_back({put[i].y,nn});
pn=nn;
}
}
for(ll i=0;i<N;i++){
for(ll j=1;j<koji[i].size();j++){
ll d=abs(koji[i][j].first-koji[i][j-1].first);
ll a=koji[i][j].second;
ll b=koji[i][j-1].second;
grana(a,b,d);
}
}
int last=novi();
grana(last,koji[g].back().second,koji[g].back().first);
int first=novi();
grana(first,koji[s].back().second,koji[s].back().first);
dist[last]=-1;
Dijkstra(first,0);
/*
for(int i=1;i<=gsz;i++)
cout<<dist[i]<<" ";
cout<<endl;
*/
ll res=dist[last];
return res;
}
Compilation message (stderr)
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:76:11: warning: statement has no effect [-Wunused-value]
76 | for(it;it!=S.end();it++){
| ^~
walk.cpp:85:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(ll j=1;j<V.size();j++){
| ~^~~~~~~~~
walk.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(ll j=1;j<koji[i].size();j++){
| ~^~~~~~~~~~~~~~~
# | 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... |