#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
long long int inf = 1e18;
struct node{
int s, e, m;
int fleb;
long long int v;
node *l,*r;
node(int S, int E, int fleba){
s = S;
e = E;
fleb = fleba;
m = (s + e)/2;
v = inf;
l = NULL;
r = NULL;
}
void update(int i, long long int k){
if(s == e){
v = min(k + s * fleb,v);
if(k == inf) v = inf;
return;
}
if(l == NULL){
l = new node(s,m,fleb);
r = new node(m + 1,e,fleb);
}
if(i <= m){
l -> update(i,k);
}
else{
r -> update(i,k);
}
v = min(l -> v, r -> v);
}
long long int query(int S, int E){
if(S <= s && e <= E){
return v;
}
long long int V = inf;
if(l == NULL) return inf;
if(S <= m){
V = min(V,l -> query(S,E));
}
if(m < S){
V += min(V,r -> query(S,E));
}
return V;
}
}*root,*froot;
vector<int> re[100100];
vector<int> er[100100];
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int N = x.size();
int M = l.size();
for(int i = 0; i < M; i++){
re[l[i]].push_back(i);
er[r[i]].push_back(i);
}
root = new node(0,1'000'000'000,1);
froot = new node(0,1'000'000'000,-1);
for(int j : re[0]){
root -> update(y[j],y[j]);
froot -> update(y[j],y[j]);
}
for(int i = 1; i < N; i++){
set<int> oobless;
set<int> ah;
for(int j : re[i]){
oobless.insert(j);
}
for(int j : er[i]){
if(oobless.find(j) != oobless.end()){
ah.insert(j);
}
}
for(int j : re[i]){
if(ah.find(j) != ah.end()) continue;
long long int num = min(root -> query(y[j],1'000'000'000) - y[j], froot -> query(0,y[j]) + y[j]);
if(num == inf) continue;
root -> update(y[j],num);
froot -> update(y[j],num);
}
if(i != N - 1){
for(int j : er[i]){
if(ah.find(j) != ah.end()) continue;
root -> update(y[j],inf);
froot -> update(y[j],inf);
}
}
}
if(root -> query(0,1'000'000'000) == inf) return -1;
return root -> query(0,1'000'000'000) + x[N - 1] - x[0];
}
int main(){
//printf("%d",min_distance({0, 4, 5, 6, 9},{6, 6, 6, 6, 6},{3, 1, 0},{4, 3, 2},{1, 3, 6},0, 4));
printf("%d",min_distance({0, 3, 5, 7, 10, 12, 14},{8, 7, 9, 7, 6, 6, 9},{0, 0, 0, 2, 2, 3, 4},{1, 2, 6, 3, 6, 4, 6},{1, 6, 8, 1, 7, 2, 5},1, 5));
}
Compilation message
walk.cpp: In function 'int main()':
walk.cpp:132:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
132 | printf("%d",min_distance({0, 3, 5, 7, 10, 12, 14},{8, 7, 9, 7, 6, 6, 9},{0, 0, 0, 2, 2, 3, 4},{1, 2, 6, 3, 6, 4, 6},{1, 6, 8, 1, 7, 2, 5},1, 5));
| ~^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| | |
| int long long int
| %lld
/usr/bin/ld: /tmp/ccFlCaGh.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKt8Ytl.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
