| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 992358 | MarwenElarbi | 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 <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=5e6;
vector<pair<int,int>> adj[nax];
vector<long long> dis(nax);
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 k=l.size();
int cnt=n;
vector<pair<int,pair<int,int>>> tab(k);
for (int i = 0; i < k; ++i)
{
tab[i]={y[i],{l[i],r[i]}};
}
sort(tab.begin(),tab.end());
map<int,pair<int,int>> mp;
for (int i = 0; i < n; ++i)
{
mp[x[i]]={i,0};
}
for (int i = 0; i < k; ++i)
{
for (int j = tab[i].se.fi; j <= tab[i].se.se; ++j)
{
if(tab[i].fi<=h[j]){
adj[cnt].pb({mp[x[j]].fi,tab[i].fi-mp[x[j]].se});
adj[mp[x[j]].fi].pb({cnt,tab[i].fi-mp[x[j]].se});
mp[x[j]]={cnt,tab[i].fi};
}
if(j>tab[i].se.fi){
adj[cnt].pb({cnt-1,x[j]-x[j-1]});
adj[cnt-1].pb({cnt,x[j]-x[j-1]});
}
cnt++;
}
}
for (int i = 0; i < cnt; ++i)
{
dis[i]=1e18;
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
pq.push({0,s});
dis[s]=0;
//cout <<"hey"<<endl;
//int t=5;
while(!pq.empty()){
//cout <<t<<endl;
//if(t==0) break;
//t--;
ll d=pq.top().fi;
ll x=pq.top().se;
//cout <<x<<" "<<d<<endl;
pq.pop();
if(x==g){
return d;
}
if(dis[x]!=d) continue;
for(auto u:adj[x]){
//cout <<"n "<<u.fi<<endl;
ll newd=u.se+d;
//cout <<u.se<<endl;
if(newd>=dis[u.fi]) continue;
dis[u.fi]=newd;
pq.push({newd,u.fi});
}
}
return -1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}