#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;
ll res = 1e18;
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 |
Execution timed out |
4038 ms |
4712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4038 ms |
4712 KB |
Time limit exceeded |
| 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 |
- |
