| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1291982 | MMihalev | Sky Walking (IOI19_walk) | C++20 | 0 ms | 0 KiB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include "walk.h"
using namespace std;
const int MAX_N=2e6+5;
const long long INF=(1LL<<60);
int N;
int sz;
map<int,int>pos;
void position(int x)
{
if(pos.find(x)==pos.end())
{
pos[x]=sz;
sz++;
}
}
long long tree[4*MAX_N][2];
void Init(int node,int l,int r)
{
tree[node][0]=INF;
tree[node][1]=INF;
if(l==r)return;
int mid=(l+r)/2;
Init(2*node,l,mid);
Init(2*node+1,mid+1,r);
}
void update(int node,int l,int r,int idx,long long val,int wh)
{
if(l==r)
{
tree[node][wh]=val;
return;
}
int mid=(l+r)/2;
if(idx<=mid)update(2*node,l,mid,idx,val,wh);
else update(2*node+1,mid+1,r,idx,val,wh);
tree[node][wh]=min(tree[2*node][wh],tree[2*node+1][wh]);
}
long long query(int node,int l,int r,int ql,int qr,int wh)
{
if(ql<=l && r<=qr)
{
return tree[node][wh];
}
int mid=(l+r)/2;
long long ans=INF;
if(ql<=mid)ans=query(2*node,l,mid,ql,qr,wh);
if(mid+1<=qr)ans=min(ans,query(2*node+1,mid+1,r,ql,qr,wh));
return ans;
}
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)
{
vector<long long>y,x;
x=X;
y=Y;
N=x.size();
if(N==1)return 0;
sz=0;
for(int i=0;i<y.size();i++)
{
position(y[i]);
}
sz--;
vector<pair<pair<int,int>,int>>fakeinters;
for(int i=0;i<l.size();i++)
{
fakeinters.push_back({{r[i],l[i]},i});
}
sort(fakeinters.begin(),fakeinters.end());
vector<pair<pair<int,int>,int>>inters;
for(int i=0;i<l.size();i++)
{
if(inters.size())
{
if(inters.back().first.first==fakeinters[i].first.first)
{
continue;
}
while(inters.size() && inters.back().first.second>=fakeinters[i].first.second)
{
inters.pop_back();
}
}
inters.push_back(fakeinters[i]);
}
Init(1,0,sz);
deque<int>active;
active.push_back(inters[0].second);
update(1,0,sz,pos[y[inters[0].second]],2LL*y[inters[0].second],+1);
update(1,0,sz,pos[y[inters[0].second]],0LL,0);
if(inters.size()==1)
{
if(inters[0].first.first==N-1 && inters[0].first.second==0)
{
return 2LL*y[inters[0].second]+1LL*x[N-1]-1LL*x[0];
}
return -1;
}
if(inters[0].first.second!=0)return -1;
for(int i=1;i<inters.size();i++)
{
int id=inters[i].second;
while(active.size() && r[active.front()]<l[id])
{
int id2=active.front();
update(1,0,sz,pos[y[id2]],INF,+1);
update(1,0,sz,pos[y[id2]],INF,0);
active.pop_front();
}
if(active.size()==0)return -1;
long long val=query(1,0,sz,pos[y[id]],sz,+1)-1LL*y[id];
val=min(val,query(1,0,sz,0,pos[y[id]],0)+1LL*y[id]);
if(i==inters.size()-1)
{
if(r[id]!=N-1)return -1;
return 1LL*x[N-1]-1LL*x[0]+val+1LL*y[id];
}
update(1,0,sz,pos[y[id]],val+1LL*y[id],+1);
update(1,0,sz,pos[y[id]],val-1LL*y[id],0);
active.push_back(id);
}
}