#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,kaf=1e9+5,inf=1e18+5;
long long n,allx[maxn],q,allh[maxn];
vector<long long>addq[maxn],delq[maxn];
struct qu{
long long l,r,res,y;
}allq[maxn];
struct segment{
struct node{
long long mina,cl,cr;
set<pair<long long,long long>>st;
node(){
mina=inf;
cl=cr=-1;
st.insert(make_pair(inf,-1));
}
}fakenode;
vector<node>seg;
segment(){
seg.resize(2);
}
long long getl(long long i){
if(seg[i].cl==-1){
seg.push_back(fakenode);
seg[i].cl=(long long)seg.size()-1;
}
return seg[i].cl;
}
long long getr(long long i){
if(seg[i].cr==-1){
seg.push_back(fakenode);
seg[i].cr=(long long)seg.size()-1;
}
return seg[i].cr;
}
void upd(long long i,long long l,long long r,long long tl,long long tr,pair<long long,long long> w){
//cout<<"upd: "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<i<<endl;
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i].st.insert(w);
seg[i].mina=(*seg[i].st.begin()).first;
return ;
}
long long m=(l+r)>>1;
upd(getl(i),l,m,tl,tr,w);
upd(getr(i),m+1,r,tl,tr,w);
seg[i].mina=min(seg[getl(i)].mina,seg[getr(i)].mina);
}
void erase(long long i,long long l,long long r,long long tl,long long tr,pair<long long,long long> w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i].st.insert(w);
seg[i].mina=(*seg[i].st.begin()).first;
return ;
}
long long m=(l+r)>>1;
erase(getl(i),l,m,tl,tr,w);
erase(getr(i),m+1,r,tl,tr,w);
seg[i].mina=min(seg[getl(i)].mina,seg[getr(i)].mina);
}
long long pors(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr||i==-1){
return inf;
}
if(l>=tl&&r<=tr){
return seg[i].mina;
}
long long m=(l+r)>>1;
return min(pors(seg[i].cl,l,m,tl,tr),pors(seg[i].cr,m+1,r,tl,tr));
}
}segmanf,segmos;
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) {
n=x.size();
q=(long long)l.size();
for(long long i=0;i<n;i++){
allx[i]=x[i];
allh[i]=h[i];
}
if(s!=0||g!=n-1){
exit(23);
return 0;
}
for(long long i=0;i<q;i++){
allq[i].l=l[i];
allq[i].r=r[i];
allq[i].y=y[i];
addq[l[i]].push_back(i);
delq[r[i]].push_back(i);
}
long long mainres=inf;
int cnt=0;
for(long long i=0;i<n;i++){
if(i==n-1){
mainres=segmos.pors(1,0,kaf-1,0,kaf-1)+allx[i];
}
for(auto x:addq[i]){
if(i==0){
allq[x].res=allq[x].y;
}else{
allq[x].res=min(segmanf.pors(1,0,kaf-1,0,allq[x].y)+allq[x].y,segmos.pors(1,0,kaf-1,allq[x].y,allh[i])-allq[x].y)+allx[i];
}
//cout<<allq[x].l<<" "<<allq[x].r<<" "<<allq[x].y<<" "<<allq[x].res<<endl;
segmos.upd(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[i]+allq[x].y,x));
segmanf.upd(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[i]-allq[x].y,x));
cnt++;
}
for(auto x:delq[i]){
segmos.erase(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[allq[x].l]+allq[x].y,x));
segmanf.erase(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[allq[x].l]-allq[x].y,x));
cnt--;
}
if(i!=n-1&&cnt==0){
return -1;
}
}
if(mainres>=inf){
mainres=-1;
}
return mainres;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4956 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
5148 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
16208 KB |
Output is correct |
| 2 |
Correct |
1489 ms |
738196 KB |
Output is correct |
| 3 |
Correct |
1355 ms |
733320 KB |
Output is correct |
| 4 |
Correct |
1366 ms |
737748 KB |
Output is correct |
| 5 |
Correct |
1383 ms |
736744 KB |
Output is correct |
| 6 |
Correct |
1376 ms |
742944 KB |
Output is correct |
| 7 |
Correct |
610 ms |
381652 KB |
Output is correct |
| 8 |
Incorrect |
1100 ms |
741028 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
16208 KB |
Output is correct |
| 2 |
Correct |
1489 ms |
738196 KB |
Output is correct |
| 3 |
Correct |
1355 ms |
733320 KB |
Output is correct |
| 4 |
Correct |
1366 ms |
737748 KB |
Output is correct |
| 5 |
Correct |
1383 ms |
736744 KB |
Output is correct |
| 6 |
Correct |
1376 ms |
742944 KB |
Output is correct |
| 7 |
Correct |
610 ms |
381652 KB |
Output is correct |
| 8 |
Incorrect |
1100 ms |
741028 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4956 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
