| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1096655 | azberjibiou | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 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];
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];
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
*/