#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define sz(x) (long long)x.size()
#define all(x) x.begin() , x.end()
const long long N = 1e18 + 7;
const long long inf = 2e18 + 7;
struct Segt{// range add update , range min query , polong long set update
struct Node{
long long left , right;
long long val , lzt;
Node():left(-1) , right(-1) , val(inf) , lzt(0ll){}
} dummy;
vector < Node > tree;
long long create_node(){
tree.push_back(dummy);
return sz(tree) - 1;
}
Segt(){
tree.resize(1);
}
void push(long long ind , long long l , long long r){
if(tree[ind].lzt){
tree[ind].val += tree[ind].lzt;
if(tree[ind].left == -1)tree[ind].left = create_node();
tree[tree[ind].left].lzt += tree[ind].lzt;
if(tree[ind].right == -1)tree[ind].right = create_node();
tree[tree[ind].right].lzt += tree[ind].lzt;
tree[ind].lzt = 0;
}
}
void set(long long ind , long long l , long long r , long long p , long long v){
push(ind,l,r);
if(l == r){
tree[ind].val = v;
return;
}
long long mid = (l + r) / 2;
if(tree[ind].left == -1)tree[ind].left = create_node();
if(tree[ind].right == -1)tree[ind].right = create_node();
if(mid >= p){
set(tree[ind].left , l , mid , p , v);
}
else{
set(tree[ind].right , mid+1 , r , p , v);
}
push(tree[ind].left , l , mid);
push(tree[ind].right , mid+1 , r);
tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
}
void set(long long p , long long v){
set(0 , 0 , N , p , v);
}
void add(long long ind , long long l , long long r , long long ql , long long qr , long long qv){
push(ind,l,r);
if(l >= ql and r <= qr){
tree[ind].lzt += qv;
push(ind,l,r);
return;
}
else if(l > qr or r < ql){
return;
}
long long mid = (l + r) / 2;
if(tree[ind].left == -1)tree[ind].left = create_node();
if(tree[ind].right == -1)tree[ind].right = create_node();
add(tree[ind].left , l , mid , ql , qr , qv);
add(tree[ind].right , mid+1 , r , ql , qr , qv);
tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
}
void add(long long l , long long r , long long v){
add(0 , 0 , N , l , r , v);
}
long long query(long long ind , long long l , long long r , long long ql , long long qr){
if(ind == -1)return inf;
push(ind,l,r);
if(l >= ql and r <= qr){
return tree[ind].val;
}
else if(l > qr or r < ql)return inf;
else{
long long mid = (l + r) / 2;
return min(query(tree[ind].left , l , mid , ql , qr) , query(tree[ind].right , mid+1 , r , ql , qr));
}
}
long long query(long long l , long long r){
return query(0 , 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) {
vector < long long > range_start[sz(X)] , range_end[sz(X)];
for(long long 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.set(0 , 0);
segt_down.set(0 , 0);
long long ans = inf;
for(long long i = 0;i<sz(X);i++){
set < long long > fuck;
vector < long long > make_updates;
for(auto itr : range_start[i]){
// cout << "STARTED : " << L[itr] << " , " << R[itr] << " , " << Y[itr] << endl;
fuck.insert(Y[itr]);
long long min_distance = min(segt_top.query(Y[itr] , H[i]) - Y[itr], segt_down.query(0 , Y[itr]) + Y[itr]);
// cout << "min_distance : " << min_distance << endl;
make_updates.push_back(min_distance);
}
for(long long j = 0;j<sz(range_start[i]);j++){
segt_top.set(Y[range_start[i][j]] , make_updates[j] + Y[range_start[i][j]]);
segt_down.set(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(fuck.count(Y[itr]) == 0){
// cout << "ENDED : " << L[itr] << " , " << R[itr] << endl;
segt_top.set(Y[itr] , inf);
segt_down.set(Y[itr] , inf);
}
}
}
if(i == 0){
segt_top.set(0 , inf);
segt_down.set(0 , inf);
}
if(i != (sz(X)-1)){
segt_top.add(1 , N , X[i+1] - X[i]);
segt_down.add(1 , N , X[i+1] - X[i]);
}
// cout << "Segt : ";for(long long i = 0;i<=10;i++)cout << segt_top.query(i,i) << " ";cout << endl;
// cout << X[i] << " : " << segt_top.query(0 , N) << endl;
// if(segt_top.query(0 , N) >= inf){
// cout << "stop : " << X[i] << endl;
// return 0ll;
// }
}
long long ret = segt_top.query(0 , H[sz(H) - 1]);
if(ret < inf)return ret;
else return -1;
}
// signed main() {
// long long n, m;
// cin >> n >> m;
// vector<long long> x(n), h(n);
// for (long long i = 0; i < n; i++)
// cin >> x[i] >> h[i];
// vector<long long> l(m), r(m), y(m);
// for (long long i = 0; i < m; i++)
// cin >> l[i] >> r[i] >> y[i];
// long long s, g;
// cin >> s >> g;
// long long result = min_distance(x, h, l, r, y, s, g);
// cout << "result : " << result << endl;
// }
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:99:12: warning: unused variable 'ans' [-Wunused-variable]
99 | long long ans = inf;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
3672 KB |
Output is correct |
2 |
Correct |
752 ms |
399544 KB |
Output is correct |
3 |
Correct |
727 ms |
401692 KB |
Output is correct |
4 |
Correct |
887 ms |
408280 KB |
Output is correct |
5 |
Correct |
905 ms |
406452 KB |
Output is correct |
6 |
Correct |
859 ms |
408740 KB |
Output is correct |
7 |
Correct |
428 ms |
208316 KB |
Output is correct |
8 |
Correct |
794 ms |
410380 KB |
Output is correct |
9 |
Correct |
750 ms |
409392 KB |
Output is correct |
10 |
Correct |
418 ms |
28476 KB |
Output is correct |
11 |
Correct |
66 ms |
4004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
87 ms |
3672 KB |
Output is correct |
2 |
Correct |
752 ms |
399544 KB |
Output is correct |
3 |
Correct |
727 ms |
401692 KB |
Output is correct |
4 |
Correct |
887 ms |
408280 KB |
Output is correct |
5 |
Correct |
905 ms |
406452 KB |
Output is correct |
6 |
Correct |
859 ms |
408740 KB |
Output is correct |
7 |
Correct |
428 ms |
208316 KB |
Output is correct |
8 |
Correct |
794 ms |
410380 KB |
Output is correct |
9 |
Correct |
750 ms |
409392 KB |
Output is correct |
10 |
Correct |
418 ms |
28476 KB |
Output is correct |
11 |
Correct |
66 ms |
4004 KB |
Output is correct |
12 |
Correct |
756 ms |
416920 KB |
Output is correct |
13 |
Correct |
939 ms |
484136 KB |
Output is correct |
14 |
Correct |
941 ms |
452556 KB |
Output is correct |
15 |
Correct |
538 ms |
138364 KB |
Output is correct |
16 |
Correct |
674 ms |
335896 KB |
Output is correct |
17 |
Correct |
686 ms |
335832 KB |
Output is correct |
18 |
Correct |
534 ms |
138372 KB |
Output is correct |
19 |
Correct |
657 ms |
335956 KB |
Output is correct |
20 |
Correct |
549 ms |
343408 KB |
Output is correct |
21 |
Correct |
145 ms |
18860 KB |
Output is correct |
22 |
Correct |
671 ms |
366488 KB |
Output is correct |
23 |
Correct |
647 ms |
368952 KB |
Output is correct |
24 |
Correct |
663 ms |
379528 KB |
Output is correct |
25 |
Correct |
703 ms |
472752 KB |
Output is correct |
26 |
Correct |
746 ms |
428824 KB |
Output is correct |
27 |
Correct |
1018 ms |
473268 KB |
Output is correct |
28 |
Correct |
914 ms |
481084 KB |
Output is correct |
29 |
Correct |
962 ms |
489960 KB |
Output is correct |
30 |
Correct |
555 ms |
347676 KB |
Output is correct |
31 |
Correct |
999 ms |
683952 KB |
Output is correct |
32 |
Correct |
401 ms |
22440 KB |
Output is correct |
33 |
Incorrect |
469 ms |
24256 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |