#include "walk.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=100050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct line{
int l, r, h;
};
int N, M;
int pos[mxN], A[mxN];
line B[mxN];
int st, en;
int sidx, eidx;
map <pii, int> vtx;
pii V[12*mxN];
int vidx;
vector <pll> adj[12*mxN];
/*
void input(){
cin >> N >> M;
for(int i=0;i<N;i++) cin >> pos[i];
for(int i=0;i<N;i++) cin >> A[i];
for(int i=1;i<=M;i++) cin >> B[i].l >> B[i].r >> B[i].h;
for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
cin >> st >> en;
}
*/
void no_endpoint(){
vector <line> v;
for(int i=1;i<=M;i++) v.push_back(B[i]);
sort(all(v), [](line a, line b){return a.h!=b.h ? a.h<b.h : a.l<b.l;});
vector <line> res;
line prev={-1, -1, -1};
for(line x : v){
if(x.h!=prev.h || prev.r<x.l){
if(prev.h!=-1) res.push_back(prev);
prev=x;
}
else prev.r=x.r;
}
if(prev.h!=-1) res.push_back(prev);
M=res.size();
for(int i=1;i<=M;i++) B[i]=res[i];
}
void init(vector <int> x, vector <int> h, vector <int> l, vector <int> r, vector <int> y, int s, int g){
N=x.size(); M=l.size();
for(int i=0;i<N;i++) pos[i]=x[i];
for(int i=0;i<N;i++) A[i]=h[i];
for(int i=1;i<=M;i++) B[i].l=l[i-1], B[i].r=r[i-1], B[i].h=y[i-1];
for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
no_endpoint();
st=s, en=g;
}
void add_edge(int a, int b, int c){
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
void add(vector <int> &v1, int val, pii rng){
if(val==-1) return;
if(val>rng.se || val<rng.fi) return;
v1.push_back(val);
}
int lb(set <int> &s, int val){
auto it=s.lower_bound(val);
return (it==s.end() ? -1 : *it);
}
int rb(set <int> &s, int val){
auto it=s.lower_bound(val+1);
if(it==s.begin()) return -1;
it--;
return *it;
}
void make_graph(){
set <int> xcr;
set <pii> fall; // x값, 끝점 index
vector <pii> hv;
for(int i=0;i<N;i++) hv.emplace_back(A[i], i);
sort(all(hv));
vector <int> turn;
for(int i=1;i<=M;i++) turn.push_back(i);
sort(all(turn), [&](int a, int b){return B[a].h>B[b].h;});
for(int now : turn){
auto [nl, nr, nh]=B[now];
while(hv.size() && hv.back().fi>=nh){
int idx=hv.back().se;
hv.pop_back();
xcr.insert(pos[idx]);
}
vector <int> cr;
vector <pii> up; // x값, 끝점 index
vector <int> down;
//get up edges
while(true){
if(fall.empty()) break;
auto it=fall.lower_bound(pii(nl, 0));
if(it==fall.end() || it->fi>nr) break;
up.push_back(*it);
fall.erase(it);
}
// add down vertices
add(down, lb(xcr, nl), pii(nl, nr));
if(nl<=pos[st] && pos[st]<=nr){
add(down, lb(xcr, pos[st]), pii(nl, nr));
add(down, rb(xcr, pos[st]), pii(nl, nr));
}
if(nl<=pos[en] && pos[en]<=nr){
add(down, lb(xcr, pos[en]), pii(nl, nr));
add(down, rb(xcr, pos[en]), pii(nl, nr));
}
add(down, rb(xcr, nr), pii(nl, nr));
sort(all(down));
down.erase(unique(all(down)), down.end());
/*
printf("nl, nr, nh=%d %d %d\n", nl, nr, nh);
for(int x : down) printf("%d ", x);
printf("\n");
printf("xcr: ");
for(int x : xcr) printf("%d ", x);
printf("\n");
*/
//make vertices
for(int x : down) cr.push_back(x);
for(auto [x, idx] : up) cr.push_back(x);
sort(all(cr));
cr.erase(unique(all(cr)), cr.end());
for(int i=0;i<cr.size();i++){
int x=cr[i];
if(vtx.count(pii(x, nh))==0){
V[vidx]=pii(x, nh);
vtx[pii(x, nh)]=vidx++;
}
//also make horizontal edges
if(i-1>=0) add_edge(vtx[pii(x, nh)], vtx[pii(cr[i-1], nh)], cr[i]-cr[i-1]);
}
//make up edges
for(auto [x, num1] : up){
int num2=vtx[pii(x, nh)];
add_edge(num1, num2, V[num1].se-nh);
}
//make down edges
for(int x : down){
fall.insert(pii(x, vtx[pii(x, nh)]));
}
}
//make st and en
V[vidx]=pii(pos[st], 0);
vtx[pii(pos[st], 0)]=vidx;
sidx=vidx++;
V[vidx]=pii(pos[en], 0);
vtx[pii(pos[en], 0)]=vidx;
eidx=vidx++;
//adding edge for st and en
auto itst=fall.lower_bound(pii(pos[st], 0));
if(itst!=fall.end() || itst->fi==pos[st]){
int nxt=itst->se;
add_edge(sidx, nxt, V[nxt].se);
}
auto iten=fall.lower_bound(pii(pos[en], 0));
if(iten!=fall.end() || iten->fi==pos[en]){
int nxt=iten->se;
add_edge(eidx, nxt, V[nxt].se);
}
/*
for(int i=0;i<vidx;i++) printf("V[%d]=%d %d\n", i, V[i].fi, V[i].se);
for(int i=0;i<vidx;i++){
printf("i=%d: ", i);
for(auto [x, y] : adj[i]) printf("(%lld %lld) ", x, y);
printf("\n");
}
*/
}
ll dist[12*mxN];
ll ans;
void dijkstra(){
for(int i=0;i<vidx;i++) dist[i]=-1;
priority_queue <pll> pq;
pq.emplace(0, sidx);
while(pq.size()){
auto [x, now]=pq.top();
pq.pop();
if(dist[now]!=-1) continue;
dist[now]=-x;
for(auto [nxt, val] : adj[now]) pq.emplace(x-val, nxt);
}
//for(int i=0;i<vidx;i++) printf("dist[%d]=%lld\n", i, dist[i]);
ans=dist[eidx];
}
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) {
init(x, h, l, r, y, s, g);
make_graph();
dijkstra();
return ans;
}
/*
int main(){
gibon
input();
make_graph();
dijkstra();
cout << ans;
}
*/
/*
7 7
0 3 5 7 10 12 14
8 7 9 7 6 6 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/
Compilation message
walk.cpp: In function 'void make_graph()':
walk.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i=0;i<cr.size();i++){
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
28456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
28504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
28504 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
28508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
32776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
32776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
28456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
28504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
