#include <cstdio>
#include <cassert>
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
#define Int long long
#define pb push_back
#define fore(i , m) for(int i = 0 ; i < m ; i++)
#define forn(i , x , y) for(int i = x ; i >= y;i--)
#define forr(i , x , y) for(int i = x ; i <= y; i++)
const Int INF = 1e18;
Int min_distance(vector<int> x, vector<int> h , vector<int> l , vector<int> r , vector<int> y , int s , int g)
{
int m = (int)l.size();
int n = (int)x.size();
gp_hash_table<int , int> degs[n];
vector<tuple<int ,int,int>> lines;
fore(i , m)
{
lines.pb({y[i] , l[i] , r[i]});
}
sort(lines.begin() , lines.end());
gp_hash_table<pair<int ,int> , vector<pair<pair<int , int> , int>>> adj;
fore(i , n)
{
degs[i][0] = i;
}
for(auto [Y , L , R] : lines)
{
forr(i , L , R)
{
degs[i][Y] = max(degs[i][Y] , R);
}
}
gp_hash_table<pair<int , int> , Int> dist;
fore(i , n)
{
if(degs[i].empty())
continue;
for(auto it = degs[i].begin() ; it != (degs[i].end()) ; it++)
{
auto [Y , R] = *it;
dist[{i , Y}] = INF;
if(R >= i + 1 && Y != 0)
{
adj[{i , Y}].pb({{i + 1 , Y} , 0});
}
if(it == prev(degs[i].end()))
break;
auto [nY , nR] = *next(it);
adj[{i , Y}].pb({{i , nY} , nY - Y});
adj[{i , nY}].pb({{i , Y} , nY - Y});
}
}
priority_queue<pair<Int , pair<int , int>>> pq;
pq.push({0 , {0 , 0}});
map<pair<Int , pair<int , int>> , int> vis;
dist[{0 , 0}] = 0;
while(!pq.empty())
{
auto tp = pq.top();
pq.pop();
if(vis[tp] == 1)
continue;
vis[tp] = 1;
auto [i , Y] = tp.second;
for(auto p : adj[{i , Y}])
{
Int w = p.second;
auto [j , nY] = p.first;
if(dist[{j , nY}] > dist[{i , Y}] + w)
{
pq.push({-dist[{i , Y}] - w , {j , nY}});
dist[{j , nY}] = w + dist[{i , Y}];
}
}
}
if(dist[{n - 1 , 0}] >= INF)
{
return -1;
}
return dist[{n - 1 , 0}] + x[n - 1] - x[0];
}
int main() {
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;
}
Compilation message
/usr/bin/ld: /tmp/ccegsSZD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccD9kpFC.o:walk.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccD9kpFC.o: in function `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)':
walk.cpp:(.text+0x19f8): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x24d8): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x26f1): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x2934): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x2fd6): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: /tmp/ccD9kpFC.o:walk.cpp:(.text+0x31d3): more undefined references to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const' follow
collect2: error: ld returned 1 exit status
