#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
struct node{long long val, l,r;};
vector<node>pre,suf;
const long long base = 1<<3;
void dodaj_synow(vector<node>&tree, long long w){
if(!tree[w].l){
tree[w].l = tree.size();
tree.push_back({1000000000000000000});
}
if(!tree[w].r){
tree[w].r = tree.size();
tree.push_back({1000000000000000000});
}
}
void ustaw(vector<node>&tree,int w, long long l, long long p, long long a, long long val){
if(a<l || p<a)return;
if(l==p)tree[w].val = val;
else{
dodaj_synow(tree, w);
ustaw(tree,tree[w].l, l, (l+p)/2, a, val);
ustaw(tree,tree[w].r, (l+p)/2+1, p, a, val);
tree[w].val = min(tree[tree[w].l].val, tree[tree[w].r].val);
}
}
long long odczyt(vector<node>&tree,int w, long long l, long long p, long long a, long long b){
if(b<l || p<a)return 1000000000000000000;
if(a<=l && p<=b){
//printf("w = %lld\n", w);
return tree[w].val;
}
else{
dodaj_synow(tree, w);
long long val = min(
odczyt(tree,tree[w].l, l, (l+p)/2, a, b),
odczyt(tree,tree[w].r, (l+p)/2+1, p, a, b)
);
tree[w].val = min(tree[tree[w].l].val, tree[tree[w].r].val);
return val;
}
}
set<pair<int,int>>poczatki;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
pre.push_back({1000000000000000000});
suf.push_back({1000000000000000000});
int n = x.size();
int m = l.size();
int i;
vector<pair<int,pair<int, int>>>zdarzenia;
zdarzenia.push_back({0,{1,0}});
for(i=0;i<m;i++){
zdarzenia.push_back({x[l[i]], {-1, y[i]}});
zdarzenia.push_back({x[r[i]], {1, y[i]}});
poczatki.insert({y[i], x[l[i]]});
}
sort(zdarzenia.begin(), zdarzenia.end());
long long wynik = 1000000000000000000;
ustaw(pre,0,0,base-1,0, 0);
ustaw(suf,0,0,base-1,0, 0);
for(auto j: zdarzenia){
if(j.first==x[n-1])
wynik = min(wynik, odczyt(suf,0, 0, base-1, j.second.second, j.second.second)+x[n-1]);
if(j.second.first==1){
//usuwanie
if(poczatki.find({j.second.second, j.first})==poczatki.end()){
ustaw(pre,0,0,base-1,j.second.second, 1000000000000000000);
ustaw(suf,0,0,base-1,j.second.second, 1000000000000000000);
}
}
if(j.second.first==-1){
//dodawanie
long long val = min({1000000000000000000ll,
odczyt(suf,0,0,base-1,j.second.second,1000000000)+j.first-j.second.second,
odczyt(pre,0,0,base-1,0,j.second.second)+j.first+j.second.second
});
// printf("%lld %lld\n", val, odczyt(suf,0,0,base-1,j.second.second,1000000000));
ustaw(pre,0,0,base-1,j.second.second, val-j.first-j.second.second);
ustaw(suf,0,0,base-1,j.second.second, val-j.first+j.second.second);
}
// printf("%d %d %d\n", j.first, j.second.second, j.second.first);
// for(auto ij:pre)printf("%lld %lld %lld\n", ij.l, ij.r, ij.val);printf("\n");
// for(auto ij:suf)printf("%lld %lld %lld\n", ij.l, ij.r, ij.val);
}
if(wynik<=1000000000000000000)
return wynik;
else
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
