#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
map<pii,int> f;
int cnt;
vector<pii> muchii[3000005];
vector<pii> nodes;
vector<int> whovert[100005],whooriz[100005];
int arb[4*100005],toprop[4*100005];
int n,m;
struct skywalk
{
ll l,r,h,ind;
} v[100005];
vector<int> X,H,L,R,Y;
bool Hdesc(int a,int b)
{
return H[a]>H[b];
}
bool Hcresc(skywalk a, skywalk b)
{
return a.h<b.h;
}
void addnode(int i,int j)
{
if(f.count({X[i],Y[j]})!=0)
return;
//cout<<X[i]<<' '<<Y[j]<<'\n';
cnt++;
f[{X[i],Y[j]}]=cnt;
nodes.push_back({i,j});
whovert[i].push_back(Y[j]);
whooriz[j].push_back(X[i]);
}
bool cresc(pii a,pii b)
{
return Y[a.second]<Y[b.second];
}
bool use[3000005];
ll dist[3000005];
ll bfs(ll s,ll g)
{
priority_queue<pll,vector<pll>,greater<pll>> coada;
for(int i=1;i<=cnt;i++)
{
dist[i]=INF;
if(nodes[i].first==s)
{
dist[i]=Y[nodes[i].second];
coada.push({dist[i],i});
}
}
ll ans=INF;
while(!coada.empty())
{
int nod=coada.top().second;
coada.pop();
if(nodes[nod].first==g)
ans=min(ans,dist[nod]+Y[nodes[nod].second]);
if(use[nod])
continue;
use[nod]=1;
for(auto i:muchii[nod])
if(dist[i.first]>dist[nod]+i.second)
{
dist[i.first]=dist[nod]+i.second;
coada.push({dist[i.first],i.first});
}
}
if(ans==INF)
return -1;
return ans;
}
void prop(int nod)
{
int val=toprop[nod];
arb[nod*2]=val;
arb[nod*2+1]=val;
toprop[nod*2]=val;
toprop[nod*2+1]=val;
}
void build(int nod,int st,int dr)
{
arb[nod]=-1;
toprop[nod]=-1;
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
if(toprop[nod]!=-1&&st!=dr)
prop(nod);
toprop[nod]=-1;
if(st>=a&&dr<=b)
{
arb[nod]=val;
toprop[nod]=val;
return;
}
int mij=(st+dr)/2;
if(a<=mij)
update(nod*2,st,mij,a,b,val);
if(b>mij)
update(nod*2+1,mij+1,dr,a,b,val);
}
int query(int nod,int st,int dr,int poz)
{
if(toprop[nod]!=-1&&st!=dr)
prop(nod);
toprop[nod]=-1;
if(st==dr)
return arb[nod];
int mij=(st+dr)/2;
if(poz<=mij)
return query(nod*2,st,mij,poz);
else
return query(nod*2+1,mij+1,dr,poz);
}
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)
{
X=x;
H=h;
L=l;
R=r;
Y=y;
n=x.size();
m=l.size();
nodes.push_back({0,0});
for(int i=0;i<m;i++)
v[i]={l[i],r[i],y[i],i};
vector<int> ups;
for(int i=0;i<n;i++)
ups.push_back(i);
sort(ups.begin(),ups.end(),Hdesc);
sort(v,v+m,Hcresc);
set<int> setik;
for(int i=0;i<n;i++)
setik.insert(i);
for(int i=0;i<m;i++)
{
bool ok=0;
if(v[i].h==7)
ok=1;
while(!ups.empty()&&H[ups.back()]<v[i].h)
{
setik.erase(ups.back());
ups.pop_back();
}
addnode(v[i].l,v[i].ind);
addnode(v[i].r,v[i].ind);
if(setik.find(s)!=setik.end())
{
if(s>=v[i].l&&s<=v[i].r)
addnode(s,v[i].ind);
}
else
{
auto it=setik.lower_bound(s);
if(it!=setik.end())
{
if((*it)>=v[i].l&&(*it)<=v[i].r)
addnode((*it),v[i].ind);
}
if(it!=setik.begin())
{
it=prev(it);
if((*it)>=v[i].l&&(*it)<=v[i].r)
addnode((*it),v[i].ind);
}
}
if(setik.find(g)!=setik.end())
{
if(g>=v[i].l&&g<=v[i].r)
addnode(g,v[i].ind);
}
else
{
auto it=setik.lower_bound(g);
if(it!=setik.end())
{
if((*it)>=v[i].l&&(*it)<=v[i].r)
addnode((*it),v[i].ind);
}
if(it!=setik.begin())
{
it=prev(it);
if((*it)>=v[i].l&&(*it)<=v[i].r)
addnode((*it),v[i].ind);
}
}
}
vector<pii> ord=nodes;
sort(ord.begin(),ord.end(),cresc);
build(1,0,n-1);
int poz=0;
for(auto i:ord)
{
while(poz<m&&v[poz].h<Y[i.second])
{
update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
poz++;
}
int val=query(1,0,n-1,i.first);
if(val!=-1)
{
if(Y[val]<=H[i.first])
addnode(i.first,val);
}
}
reverse(ord.begin(),ord.end());
reverse(v,v+m);
build(1,0,n-1);
poz=0;
for(auto i:ord)
{
while(poz<m&&v[poz].h>Y[i.second])
{
update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
poz++;
}
int val=query(1,0,n-1,i.first);
if(val!=-1)
{
if(Y[val]<=H[i.first])
addnode(i.first,val);
}
}
for(int i=0;i<n;i++)
{
sort(whovert[i].begin(),whovert[i].end());
for(int j=1;j<whovert[i].size();j++)
{
int ya=whovert[i][j-1];
int yb=whovert[i][j];
int a=f[{X[i],ya}];
int b=f[{X[i],yb}];
muchii[a].push_back({b,yb-ya});
muchii[b].push_back({a,yb-ya});
}
}
for(int i=0;i<m;i++)
{
sort(whooriz[i].begin(),whooriz[i].end());
for(int j=1;j<whooriz[i].size();j++)
{
int xa=whooriz[i][j-1];
int xb=whooriz[i][j];
int a=f[{xa,Y[i]}];
int b=f[{xb,Y[i]}];
muchii[a].push_back({b,xb-xa});
muchii[b].push_back({a,xb-xa});
}
}
return bfs(s,g);
}
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:152:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
152 | bool ok=0;
| ^~
walk.cpp:244:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | for(int j=1;j<whovert[i].size();j++)
| ~^~~~~~~~~~~~~~~~~~
walk.cpp:258:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | for(int j=1;j<whooriz[i].size();j++)
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
81240 KB |
Output is correct |
| 2 |
Correct |
17 ms |
81272 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
81244 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
81908 KB |
Output is correct |
| 2 |
Correct |
17 ms |
81240 KB |
Output is correct |
| 3 |
Correct |
1245 ms |
153668 KB |
Output is correct |
| 4 |
Correct |
1296 ms |
157264 KB |
Output is correct |
| 5 |
Correct |
760 ms |
144648 KB |
Output is correct |
| 6 |
Correct |
726 ms |
139944 KB |
Output is correct |
| 7 |
Correct |
767 ms |
145220 KB |
Output is correct |
| 8 |
Correct |
1238 ms |
161728 KB |
Output is correct |
| 9 |
Correct |
1130 ms |
155024 KB |
Output is correct |
| 10 |
Correct |
1415 ms |
164328 KB |
Output is correct |
| 11 |
Correct |
994 ms |
142936 KB |
Output is correct |
| 12 |
Correct |
642 ms |
125536 KB |
Output is correct |
| 13 |
Correct |
1391 ms |
167760 KB |
Output is correct |
| 14 |
Correct |
446 ms |
122204 KB |
Output is correct |
| 15 |
Incorrect |
481 ms |
123560 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
97008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
97008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
81240 KB |
Output is correct |
| 2 |
Correct |
17 ms |
81272 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
81244 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
