#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int mostll=11;
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;
}
bool pox(zgrada a,zgrada b){
return a.x<b.x;
}
set<ll> S;
vector<pair<ll,ll>> graf[12*maxn];
vector<ll> presek[maxn];
bool prosli[12*maxn];
ll dist[12*maxn];
priority_queue<pair<ll,ll>> PQ;
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) {
s++;
g++;
N=x.size();
M=l.size();
for(ll i=1;i<=N;i++){
niz[i].x=x[i-1];
niz[i].y=h[i-1];
niz[i].id=i;
}
for(ll i=1;i<=M;i++){
put[i].l=l[i-1]+1;
put[i].r=r[i-1]+1;
put[i].y=y[i-1];
}
sort(niz+1,niz+1+N,poy);
sort(put+1,put+1+M,cmpsw);
ll pok=N;
niz[0].y=0;
for(ll i=M;i>=1;i--){
while(niz[pok].y>=put[i].y){
S.insert(niz[pok].id);
pok--;
}
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);
presek[*it].push_back(i);
}
/* cout<<"PUT "<<put[i].l<<" "<<put[i].r<<" "<<put[i].y<<" SECE"<<endl;
for(ll x:V)
cout<<x<<" ";
cout<<endl;
*/
for(ll j=1;j<V.size();j++){
ll pr=V[j-1];
ll tr=V[j];
ll d=x[tr-1]-x[pr-1];
// cout<<d<<" ";
pr=(pr-1)*mostll+presek[pr].size();
tr=(tr-1)*mostll+presek[tr].size();
graf[pr].push_back({tr,d});
graf[tr].push_back({pr,d});
}
// cout<<endl;
}
for(ll i=1;i<=N;i++){
for(ll j=1;j<presek[i].size();j++){
ll d=put[presek[i][j-1]].y-put[presek[i][j]].y;
ll a=(i-1)*mostll+j;
ll b=(i-1)*mostll+j+1;
graf[a].push_back({b,d});
graf[b].push_back({a,d});
}
}
/*for(ll i=1;i<=mostll*N;i++){
cout<<i<<": ";
for(auto x:graf[i])
cout<<x.first<<" "<<x.second<<" ";
cout<<endl;
}*/
Dijkstra(presek[s].size()+(s-1)*mostll,put[presek[s].back()].y);
ll res=1e18;
for(ll i=0;i<presek[g].size();i++){
if(dist[(g-1)*mostll+i+1]==0)
continue;
ll d=dist[(g-1)*mostll+i+1];
d+=put[presek[g][i]].y;
res=min(res,d);
}
if(res==1e18)
return -1;
return res;
}
Compilation message
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:70:11: warning: statement has no effect [-Wunused-value]
70 | for(it;it!=S.end();it++){
| ^~
walk.cpp:83: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]
83 | for(ll j=1;j<V.size();j++){
| ~^~~~~~~~~
walk.cpp:96: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]
96 | for(ll j=1;j<presek[i].size();j++){
| ~^~~~~~~~~~~~~~~~~
walk.cpp:115:14: 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]
115 | for(ll i=0;i<presek[g].size();i++){
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
33112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
33116 KB |
Output is correct |
| 3 |
Correct |
7 ms |
33116 KB |
Output is correct |
| 4 |
Runtime error |
32 ms |
67240 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33364 KB |
Output is correct |
| 2 |
Correct |
7 ms |
33112 KB |
Output is correct |
| 3 |
Incorrect |
618 ms |
118308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
49624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
49624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
33112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
33116 KB |
Output is correct |
| 3 |
Correct |
7 ms |
33116 KB |
Output is correct |
| 4 |
Runtime error |
32 ms |
67240 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
