#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
#define int long long
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<signed> 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<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed 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++)
{
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:242:22: 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]
242 | for(int j=1;j<whovert[i].size();j++)
| ~^~~~~~~~~~~~~~~~~~
walk.cpp:256:22: 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]
256 | for(int j=1;j<whooriz[i].size();j++)
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
82280 KB |
Output is correct |
| 2 |
Correct |
17 ms |
82392 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
82520 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
82476 KB |
Output is correct |
| 2 |
Correct |
17 ms |
82524 KB |
Output is correct |
| 3 |
Correct |
1290 ms |
181632 KB |
Output is correct |
| 4 |
Correct |
1399 ms |
186908 KB |
Output is correct |
| 5 |
Correct |
859 ms |
165556 KB |
Output is correct |
| 6 |
Correct |
805 ms |
158304 KB |
Output is correct |
| 7 |
Correct |
872 ms |
165860 KB |
Output is correct |
| 8 |
Correct |
1480 ms |
190440 KB |
Output is correct |
| 9 |
Correct |
1224 ms |
179800 KB |
Output is correct |
| 10 |
Correct |
1514 ms |
190876 KB |
Output is correct |
| 11 |
Correct |
1043 ms |
162248 KB |
Output is correct |
| 12 |
Correct |
648 ms |
134104 KB |
Output is correct |
| 13 |
Correct |
1517 ms |
196824 KB |
Output is correct |
| 14 |
Correct |
489 ms |
131564 KB |
Output is correct |
| 15 |
Incorrect |
494 ms |
133724 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
101320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
101320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
82280 KB |
Output is correct |
| 2 |
Correct |
17 ms |
82392 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
82520 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
