#include "walk.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const ll INFL=0x3f3f3f3f3f3f3f3f;
struct st{
int l,r,y;
};
static map<P,int>mp;
static ll d[2000000];
static int cnt=0;
static vector<P>E[2000000];
void add_edge(P a,P b,ll dist){
if(!mp.count(a)){
mp[a]=cnt++;
}
if(!mp.count(b)){
mp[b]=cnt++;
}
E[mp[a]].push_back(P(dist,mp[b]));
E[mp[b]].push_back(P(dist,mp[a]));
}
struct Segtree{
int N;
vector<ll>dat;
Segtree(int n){
N=1;while(N<n)N<<=1;
dat=vector<ll>(2*N);
}
void update(int k,ll x){
k+=N;
dat[k]=x;
while(k>1){
k>>=1;
dat[k]=min(dat[k*2],dat[k*2+1]);
}
}
ll query(int l,int r){
ll res=INFL;
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)res=min(res,dat[l++]);
if(r&1)res=min(res,dat[--r]);
}
return res;
}
};
set<int>vl[200000],vr[200000];
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) {
int n=x.size();
int m=l.size();
if(s==0&&g==n-1){
vector<int>ys{0};
rep(i,m){
vl[r[i]].insert(y[i]);
vr[l[i]].insert(y[i]);
ys.push_back(y[i]);
}
vl[s].insert(0);
vr[g].insert(0);
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
rep(i,n){
for(int j:vr[i]){
vl[i].erase(j);
}
}
Segtree seg1(ys.size()),seg2(ys.size());
rep(i,ys.size()){
seg1.update(i,INFL);
seg2.update(i,INFL);
}
seg1.update(0,0);
seg2.update(0,0);
rep(i,n){
//~ cout<<"---"<<i<<endl;
//~ rep(j,ys.size()){
//~ cout<<seg1.query(j,j+1)<<' ';
//~ }
//~ cout<<endl;
//~ rep(j,ys.size()){
//~ cout<<seg2.query(j,j+1)<<' ';
//~ }
//~ cout<<endl;
for(int jh:vr[i]){
//~ cout<<jh<<endl;
int j=lower_bound(ys.begin(),ys.end(),jh)-ys.begin();
ll A=seg1.query(0,j+1);
A=(A>=INFL?INFL:A+jh);
int k=upper_bound(ys.begin(),ys.end(),h[i])-ys.begin();
ll B=seg2.query(j,k);
B=(B>=INFL?INFL:B-jh);
ll C=min(A,B);
if(C==INFL){seg1.update(j,INFL);seg2.update(j,INFL);}
else{
seg1.update(j,C-jh);
seg2.update(j,C+jh);
}
}
for(int jh:vl[i]){
int j=lower_bound(ys.begin(),ys.end(),jh)-ys.begin();
seg1.update(j,INFL);
seg2.update(j,INFL);
}
}
ll ans=x.back()+seg1.query(0,1);
if(ans>=INFL)return -1;
return ans;
}
return 12345;
/*
mp.clear();
cnt=0;
rep(i,n)E[i].clear();
vector<st>H;
rep(i,m){
H.push_back({l[i],r[i],y[i]});
}
sort(H.begin(),H.end(),[](st a,st b){return a.y>b.y;});
vector<P>V;
rep(i,n){
V.push_back(P(h[i],i));
}
sort(V.begin(),V.end(),[](P a,P b){return a.first>b.first;});
set<int>se;
int cur=0;
for(auto&p:H){
while(cur<V.size()&&V[cur].first>=p.y){
se.insert(V[cur].second);
cur++;
}
auto it=se.lower_bound(p.l);
while(it!=se.end()&&*it<p.r){
int L=*it;
it++;
int R=*it;
add_edge(P(L,p.y),P(R,p.y),x[R]-x[L]);
}
}
map<int,vector<int>>mp_v;
mp_v[s].push_back(0);
mp_v[g].push_back(0);
for(auto&p:mp){
mp_v[p.first.first].push_back(p.first.second);
}
for(auto&v:mp_v){
rep(i,int(v.second.size())-1){
add_edge(P(v.first,v.second[i]),P(v.first,v.second[i+1]),v.second[i+1]-v.second[i]);
}
}
if(!mp.count(P(s,0))||!mp.count(P(g,0)))return -1;
priority_queue<P,vector<P>,greater<P>>que;
memset(d,0x3f,sizeof(d));
d[mp[P(s,0)]]=0;
que.push(P(0,mp[P(s,0)]));
while(!que.empty()){
P p=que.top();que.pop();
if(d[p.second]!=p.first)continue;
for(P&u:E[p.second]){
if(d[u.second]>p.first+u.first){
d[u.second]=p.first+u.first;
que.push(P(d[u.second],u.second));
}
}
}
ll ans=d[mp[P(g,0)]];
if(ans==INFL)return -1;
return ans;*/
}
Compilation message
walk.cpp:15:11: warning: 'd' defined but not used [-Wunused-variable]
15 | static ll d[2000000];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
66028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
66060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
72168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
72168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
66028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
