#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
struct walk{
ll l,r,y;
};
vector <walk> all;
const ll MAXN = 1e5 + 100;
const ll INF = 1e18;
ll dp[MAXN];
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){
ll m = sz(l);
ll n = sz(x);
for (ll i = 0;i < m;i ++){
all.push_back({l[i],r[i],y[i]});
}
// sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.y>a2.y;});
// vector <ll> order;
// order.resize(n);
// iota(order.begin(),order.end(),0);
// sort(order.begin(),order.end(),[&](ll x,ll y){return h[x] > h[y];});
//// cout<<"OK"<<endl;
// {
// set <ll> s;
// s.insert(-1);
// s.insert(n);
// for (ll i = 0,ptr = 0;i < n;i ++){
// while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
// s.insert(order[ptr]);
// ptr++;
// }
// all[i].l = *lower_bound(s.begin(),s.end(),all[i].l);
// all[i].r = *prev(upper_bound(s.begin(),s.end(),all[i].r));
// }
// }
sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.r<a2.r;});
vector <pll> event;
for (ll i = 0;i < n;i ++){
if (all[i].l > all[i].r)continue;
event.push_back(MP(all[i].l,i));
event.push_back(MP(all[i].r+1,i));
}
// cout<<"OK"<<endl;
sort(event.begin(),event.end());
memset(dp,0x3f,sizeof dp);
set <pll> s;
// return -1;
ll res = INF;
for (ll i = 0,ptr = 0;i < m;i ++){
// cout<<i<<endl;
if (all[i].l > all[i].r)continue;
while (ptr < sz(event) && event[ptr].fi <= all[i].r){
pll x;
x.se = event[ptr].se;
x.fi = all[x.se].y;
if (s.find(x) != s.end())s.erase(x);
else s.insert(x);
// cout<<ptr<<endl;
ptr++;
}
// cout<<i<<' '<<dp[i]<<endl;
if (all[i].l == 0)dp[i] = all[i].y;
auto tmp = s.find(MP(all[i].y,i));
if (tmp != s.begin())dp[(*prev(tmp)).se] = min(dp[(*prev(tmp)).se],dp[i] + abs((*prev(tmp)).fi - all[i].y));
// if (next(tmp) != s.end())dp[(*next(tmp)).se] = min(dp[(*next(tmp)).se],dp[i] + abs((*next(tmp)).fi - all[i].y));
if (all[i].r == n - 1)res = min(res,dp[i] + x[n-1]-x[0]+all[i].y);
}
if (res==INF)res=-1;
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
4308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
