#include "walk.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
ll solve_subtask_1_2(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){
}
template<typename T>
struct li_chao_tree{
ll N;
vector<std::pair<T,T>> lines;
vector<T> x;
std::map<ll,ll> rev;
li_chao_tree(vector<T> X, T xINF){
N = 1;
while(N <= x.size()) N *= 2;
lines.resize(2*N, mp(0,inf));
x.resize(N);
rep(i,0,N){
if(i < X.size()){
x[i] = X[i];
rev[x[i]] = i;
}
else x[i] = xINF;
}
}
ll ID(T X){
return rev[X];
}
T value(std::pair<T,T> line, T X){
return line.first*X+line.second;
}
void add_segment(ll a, ll b, std::pair<T,T> line, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(b <= l || r <= a) return;
if(a <= l && r <= b){
if(N <= now){
if(value(lines[now], x[l]) > value(line, x[l])) lines[now] = line;
return;
}
ll m = (l+r)/2;
bool left = (value(lines[now],x[l]) < value(line, x[l]));
bool mid = (value(lines[now],x[m]) < value(line, x[m]));
bool right = (value(lines[now],x[r]) < value(line, x[r]));
if(left && mid && right){
std::swap(line, lines[now]);
return;
}
if(!left && !mid && !right){
return;
}
if(left && mid){
std::swap(line, lines[now]);
add_segment(a,b,line,now*2+1,m,r);
return;
}
if(mid && right){
std::swap(line, lines[now]);
add_segment(a,b,line,now*2,l,m);
return;
}
if(left){
add_segment(a,b,line,now*2,l,m);
return;
}
if(right){
add_segment(a,b,line,now*2+1,m,r);
return;
}
}
else{
add_segment(a,b,line,now*2,l,(l+r)/2);
add_segment(a,b,line,now*2+1,(l+r)/2,r);
}
}
T calc(ll idx, T X){
T ret = inf;
idx += N;
while(idx){
ret = std::min(idx, value(lines[idx], X));
idx /= 2;
}
return ret;
}
};
template<typename T>
struct segment_tree{
ll N;
vector<T> node;
ll valINF;
segment_tree(int n, ll valINF_): valINF(valINF_){
N = 1;
while(N <= n) N *= 2;
node.resize(2*N, valINF);
}
void set(ll idx, T val){
idx += N;
node[idx] = val;
idx /= 2;
while(idx){
node[idx] = compare(node[idx*2], node[idx*2+1]);
idx /= 2;
}
}
T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(b <= l || r <= a) return valINF;
if(a <= l && r <= b) return node[now];
return compare(calc(a,b,now*2,l,(l+r)/2), calc(a,b,now*2+1,(l+r)/2,r));
}
T compare(T l, T r){
return std::min(l, r);
}
};
void dec(std::map<ll,ll> &map, ll el){
map[el]--;
if(map[el] == 0) map.erase(el);
}
ll solve_subtask_3_4(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 N = x.size();
vi y_mem;
std::map<ll,ll> mem;
ll M = 0;
{
mem[0] = 0;
for(auto el: h) mem[el] = 0;
for(auto el: y) mem[el] = 0;
for(auto &el: mem){
y_mem.pb(el.first);
el.second = M++;
}
}
segment_tree<ll> left(M, inf), right(M, inf);
vector<std::map<ll,ll>> value(M);
rep(i,0,M) value[i][inf] = 1;
vii erase_idx(N), erase_val(N);
vii add(N);
rep(i,0,l.size()){
add[l[i]].pb(i);
}
rep(t,0,N){
for(auto i: add[t]){
ll val = left.calc(0, mem[y[i]]+1)+y[i];
val = std::min(val, right.calc(mem[y[i]], mem[h[i]]+1)-y[i]);
if(t == 0) val = y[i];
value[mem[y[i]]][val]++;
left.set(mem[y[i]], (*value[mem[y[i]]].begin()).first-y[i]);
right.set(mem[y[i]], (*value[mem[y[i]]].begin()).first+y[i]);
erase_idx[r[i]].pb(y[i]);
erase_val[r[i]].pb(val);
}
if(t == N-1) break;
rep(i,0,erase_idx[t].size()){
ll Y = erase_idx[t][i];
ll V = erase_val[t][i];
dec(value[mem[Y]], V);
left.set(mem[Y], (*value[mem[Y]].begin()).first-Y);
right.set(mem[Y], (*value[mem[Y]].begin()).first+Y);
}
}
ll ans = right.calc(0,M)+x[N-1]-x[0];
if(ans >= inf/2) ans = -1;
return ans;
}
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 N = x.size();
//if(s == 0 && g == N-1)
return solve_subtask_3_4(x,h,l,r,y,s,g);
return -1;
}
Compilation message
walk.cpp: In function 'll solve_subtask_1_2(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
30 | }
| ^
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:200:5: warning: unused variable 'N' [-Wunused-variable]
200 | ll N = x.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
6140 KB |
Output is correct |
| 2 |
Incorrect |
385 ms |
30748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
6140 KB |
Output is correct |
| 2 |
Incorrect |
385 ms |
30748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
