#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 1e5 + 7;
const int inf = 2e9 + 7;
struct Segt{// range add update , range min query , point set update
int tree[4 * N] , lzt[4 * N];
Segt(){
fill(tree , tree + 4 * N , inf);
memset(lzt , 0 , sizeof(lzt));
}
void push(int ind , int l , int r){
if(lzt[ind]){
if(tree[ind] < inf)tree[ind] += lzt[ind];
if(l != r){
lzt[ind*2] += lzt[ind];
lzt[ind*2+1] += lzt[ind];
}
lzt[ind] = 0;
}
}
void update_add(int ind , int l , int r , int ql , int qr , int qv){
push(ind,l,r);
if(l >= ql and r <= qr){
lzt[ind] += qv;
push(ind,l,r);
return;
}
else if(l > qr or r < ql){
return;
}
int mid = (l + r) >> 1;
update_add(ind*2 , l , mid , ql , qr , qv);
update_add(ind*2+1 , mid+1 , r, ql , qr , qv);
tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
}
void update_add(int l , int r , int v){
update_add(1 , 0 , N , l , r , v);
}
void update_set(int ind , int l , int r , int qp , int qv){
push(ind,l,r);
if(l == r){
tree[ind] = qv;
return;
}
int mid = (l + r) >> 1;
if(mid >= qp){
update_set(ind*2 , l , mid , qp , qv);
}
else {
update_set(ind*2+1 , mid+1 , r , qp , qv);
}
push(ind*2 , l , mid);
push(ind*2+1 , mid+1 , r);
tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
}
void update_set(int p , int v){
update_set(1 , 0 , N , p , v);
}
int query(int ind , int l , int r , int ql , int qr){
push(ind,l,r);
if(l >= ql and r <= qr)return tree[ind];
else if(l > qr or r < ql)return inf;
int mid = (l + r) >> 1;
return min(query(ind*2 , l , mid , ql , qr) , query(ind*2+1 , mid+1 , r , ql , qr));
}
int query(int l , int r){
return query(1 , 0 , N , l , r);
}
};
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
// cout << "flag-1" << endl;
vector < int > cmp = {0};
for(auto itr : H)cmp.push_back(itr);
for(auto itr : Y)cmp.push_back(itr);
sort(all(cmp));
cmp.resize(unique(all(cmp)) - cmp.begin());
// cout << "cmp : ";for(auto itr : cmp)cout << itr << " ";cout << endl;
vector < int > cmp_h , cmp_y;
for(auto itr : H){
cmp_h.push_back(lower_bound(all(cmp) , itr) - cmp.begin());
}
for(auto itr : Y){
cmp_y.push_back(lower_bound(all(cmp) , itr) - cmp.begin());
}
vector < int > range_start[sz(X)] , range_end[sz(X)];
for(int i = 0;i<sz(L);i++){
range_start[L[i]].push_back(i);
range_end[R[i]].push_back(i);
}
Segt segt_top , segt_down;
segt_top.update_set(0 , 0);
segt_down.update_set(0 , 0);
auto cntvec = [&](vector < int > &vec , int &b){
auto it = lower_bound(all(vec) , b);
if(it == vec.end())return false;
else return (*it) == b;
};
int ans = inf;
for(int i = 0;i<sz(X);i++){
// cout << "X : " << X[i] << endl;
// cout << "X : " << X[i] << endl;
// cout << "segt_top : " << endl;
// for(int j = 0;j<sz(cmp);j++)cout << cmp[j] << " : " << segt_top.query(j , j) - cmp[j] << endl;
// cout << "segt_down : " << endl;
// for(int j = 0;j<sz(cmp);j++)cout << cmp[j] << " : " << segt_down.query(j , j) - cmp[j] << endl;
// cout << "segt_down : " << endl;
// for(int j = 0;j<sz(cmp);j++)cout << cmp[j] << " : " << segt_down.query(j , j) << endl;
vector < int > starts_here;
vector < int > make_updates;
for(auto itr : range_start[i]){
starts_here.push_back(itr);
int min_distance = min(segt_top.query(cmp_y[itr] , cmp_h[itr]) - Y[itr], segt_down.query(0 , cmp_y[itr]) + Y[itr]);
// cout << "min_distance " << Y[itr] << " : " << min_distance << endl;
// cout << "res top : " << segt_top.query(cmp_y[itr] , cmp_h[itr]) - Y[itr] << endl;
// cout << "res down : " << segt_down.query(0 , cmp_y[itr]) + Y[itr] << endl;
make_updates.push_back(min_distance);
}
for(int j = 0;j<sz(range_start[i]);j++){
segt_top.update_set(cmp_y[range_start[i][j]] , make_updates[j] + Y[range_start[i][j]]);
segt_down.update_set(cmp_y[range_start[i][j]] , make_updates[j] - Y[range_start[i][j]]);
}
if(i != (sz(X)-1)){
for(auto itr : range_end[i]){
if(cntvec(starts_here , itr) == 0){
// cout << "ENDS : " << Y[itr] << endl;
segt_top.update_set(cmp_y[itr] , inf);
segt_down.update_set(cmp_y[itr] , inf);
}
}
}
if(i == 0){
segt_top.update_set(0 , inf);
segt_down.update_set(0 , inf);
}
if(i != (sz(X)-1)){
segt_top.update_add(1 , N , X[i+1] - X[i]);
segt_down.update_add(1 , N , X[i+1] - X[i]);
}
// cout << "segt_top : " << endl;
// for(int j = 0;j<sz(cmp);j++)cout << cmp[j] << " : " << segt_top.query(j , j) - cmp[j] << endl;
// cout << endl;
}
return segt_top.query(0 , cmp_h[sz(H) - 1]);
}
Compilation message
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:102:6: warning: unused variable 'ans' [-Wunused-variable]
102 | int ans = inf;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
10680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
10680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
