#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++)
struct chash {
Int operator()(pair<Int ,Int> x) const { return x.first* 31ll + x.second; }
};
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();
map<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());
map<pair<Int ,Int> , vector<pair<pair<Int , Int> , Int>> > adj;
fore(i , n)
{
degs[i][0] = i;
}
vector<Int> mxR(n , 0);
for(auto [Y , L , R] : lines)
{
forr(i , L , R)
{
degs[i][Y] = max(degs[i][Y] , R);
mxR[i] = max(mxR[i] , R);
}
}
fore(i , n - 1)
{
if(mxR[i] <= i)
{
return -1ll;
}
}
map<pair<Int , Int> , Int > dist;
fore(i , n)
{
if(degs[i].empty())
{
return -1ll;
}
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 , Int> , Int > vis;
dist[{0 , 0}] = 0;
while(!pq.empty())
{
auto tp = pq.top();
pq.pop();
if(vis[tp.second] == 1)
continue;
vis[tp.second] = 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 -1ll;
}
return dist[{n - 1 , 0}] + x[n - 1] - x[0];
}
//signed 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;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
28836 KB |
Output is correct |
| 2 |
Execution timed out |
4082 ms |
910136 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
28836 KB |
Output is correct |
| 2 |
Execution timed out |
4082 ms |
910136 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
