#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int base = 1<<17;
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int v){
if(a<=l && p<=b){
tree[w] = v;
return;
}
if(b<l || p<a)return;
if(tree[w]!=-1)
tree[w*2] = tree[w*2+1] = tree[w];
ustaw(w*2, l, (l+p)/2, a, b, v);
ustaw(w*2+1, (l+p)/2+1, p, a, b, v);
tree[w] = -1;
}
int odczyt(int w){
int res = -1;
w+=base;
while(w>0){
if(tree[w]!=-1)
res = tree[w];
w/=2;
}
return res;
}
vector<int>l,r,y,x;
void dodaj(int a, int b, int h){
l.push_back(a);
r.push_back(b);
y.push_back(h);
}
vector<pair<int,long long>>graf[700010];
long long dist[700010];
bool odw[700010];
map<pair<int,int>,int>mapa;
long long odl(pair<int,int>a, pair<int,int>b){
return abs(a.second-b.second);
}
long long odl1(pair<int,int>a, pair<int,int>b){
return abs(x[a.first]-x[b.first]);
}
map<int,set<int>>poziomy;
long long min_distance(vector<int> X, vector<int> h, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
x = X;
// podzielic kazda pozioma
// dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy
vector<tuple<int,int,int,int>>przedzialy;
int n = x.size();
int m = L.size();
int i;
if(s>g)swap(s,g);
for(i=0;i<m;i++){
poziomy[Y[i]].insert(L[i]);
if(L[i]<s && R[i]>g){
// printf("%d 3\n", i);
dodaj(L[i],s,Y[i]);
dodaj(s,g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else if(L[i]<s && R[i]>s){
// printf("%d 2\n", i);
dodaj(L[i],s,Y[i]);
dodaj(s,R[i],Y[i]);
}
else if(g<R[i] && L[i]<g){
// printf("%d 2\n", i);
dodaj(L[i],g,Y[i]);
dodaj(g,R[i],Y[i]);
}
else{
// printf("%d 1\n");
dodaj(L[i],R[i],Y[i]);
}
}
m = l.size();
//for(i=0;i<m;i++)printf("%d %d %d %d\n", y[i], l[i], r[i], i);printf("\n");
for(i=0;i<m;i++)
przedzialy.push_back({y[i],l[i],r[i],0});
sort(przedzialy.begin(), przedzialy.end());
for(i=0;i<m;i++)
get<3>(przedzialy[i]) = i;
for(i=0;i<n;i++)tree[i+base] = -1;
for(i=base-1;i>0;i--)
tree[i] = -1;
ustaw(1, 0,base-1,s,s,0);
ustaw(1, 0,base-1,g,g,0);
mapa[{s,0}]=0;
mapa[{g,0}]=1;
for(auto j: przedzialy){
auto [Y,L,R,i] = j;
int a = odczyt(L);
if(a!=-1 && mapa.find({L, a})==mapa.end())
mapa[{L,a}] = mapa.size();
a = odczyt(R);
if(a!=-1 &&mapa.find({R, a})==mapa.end())
mapa[{R,a}] = mapa.size();
if(mapa.find({R, Y})==mapa.end())
mapa[{R,Y}] = mapa.size();
if(mapa.find({L, Y})==mapa.end())
mapa[{L,Y}] = mapa.size();
ustaw(1, 0, base-1, L, R, Y);
/*
for(int ij=0;ij<2;ij++){
int a = odczyt(ij?R:L);
int s = (a-2)/2;
b = i*2+2+ij;
// if(ij==0)printf("LEWY: %d %d(%d)\n", b, a,s);
// else printf("PRAWY: %d %d(%d)\n", b, a,s);
if(a==-1)continue;
if(a==0 || a==1){
graf[b].push_back({a,Y});
graf[a].push_back({b,Y});
}
else{
long long d;
d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<1>(przedzialy[s])]);
graf[b].push_back({a, d});
graf[a].push_back({b, d});
d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<2>(przedzialy[s])]);
graf[b].push_back({a^1, d});
graf[a^1].push_back({b, d});
}
}
graf[b].push_back({b-1, abs(x[L]-x[R])});
graf[b-1].push_back({b, abs(x[L]-x[R])});
ustaw(1, 0, base-1, L, R, b-1);*/
// printf("%d %d %d: %d %d\n", y[i], l[i], r[i], b-1, b);
}/*
for(i=0;i<(int)przedzialy.size()*2+2;i++){
printf("%d: ", i);
for(auto j: graf[i])
printf("%d-%d ", j.first, j.second);
printf("\n");
}*/
vector<pair<pair<int,int>,int>>wartosci;
for(auto j=mapa.begin();j!=mapa.end();j++){
auto xd = *j;
wartosci.push_back({xd.first, xd.second});
auto next = j;
next++;
if(next==mapa.end())break;
if((*next).first.first==(*j).first.first){
graf[(*next).second].push_back({(*j).second, odl((*j).first, (*next).first)});
graf[(*j).second].push_back({(*next).second, odl((*j).first, (*next).first)});
}
}
mapa.clear();
for(auto j:wartosci)
mapa[{j.first.second,j.first.first}]=j.second;
for(auto j=mapa.begin();j!=mapa.end();j++){
if((*j).first.first==0)continue;
auto next = j;
next++;
if(next==mapa.end())break;
if((*next).first.first==(*j).first.first){
int a =(*j).first.second, b = (*next).first.second;
if(a==b || poziomy[(*next).first.first].upper_bound(a)==poziomy[(*next).first.first].end()||*(poziomy[(*next).first.first].lower_bound(a))<b){
graf[(*next).second].push_back({(*j).second, x[(*next).first.second]-x[(*j).first.second]});
graf[(*j).second].push_back({(*next).second, x[(*next).first.second]-x[(*j).first.second]});
}
}
}/*
for(auto j: wartosci)printf("%d %d %d\n", j.second, j.first.first, j.first.second);
for(i=0;i<10;i++){
printf("%d: ", i);
for(auto j: graf[i])printf("%d-%d ", j.first,j.second);printf("\n");
}*/
priority_queue<pair<long long, int>>kolejka;
dist[0] = 1;
kolejka.push({-1,0});
while(kolejka.size()){
auto a = kolejka.top();
//printf("%lld %d %d\n", -a.first, a.second);
kolejka.pop();
if(odw[a.second])continue;
odw[a.second]=1;
for(auto j: graf[a.second]){
if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){
dist[j.first]=dist[a.second]+j.second;
kolejka.push({-dist[j.first], j.first});
}
}
}
return dist[1]-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
35784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
35784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
21340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
