Submission #1291398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291398		MMihalev	Sky Walking (IOI19_walk)	C++20	0 / 100	14 ms	2624 KiB

walk

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include "walk.h"
using namespace std;
const int MAX_N=1e5+5;
const long long INF=(1LL<<60);
int N;
int sz=0;
map<int,int>pos;
int position(int x)
{
    if(pos.find(x)==pos.end())
    {
        pos[x]=sz++;
    }
    return pos[x];
}

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)
{
    N=x.size();
    sz=0;

    for(int i=0;i<y.size();i++)
    {
        pos[y[i]]=position(y[i]);
    }

    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]);
    }

    deque<int>active;
    active.push_back(inters[0].second);
    update(1,1,sz,pos[y[inters[0].second]],y[inters[0].second],+1);
    update(1,1,sz,pos[y[inters[0].second]],-y[inters[0].second],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;
    }

    for(int i=1;i<inters.size();i++)
    {
        int id=inters[i].second;

        if(active.size()==0)return -1;

        while(active.size() && r[active.front()]<l[id])
        {
            int id2=active.front();
            update(1,1,sz,pos[y[id2]],INF,+1);
            update(1,1,sz,pos[y[id2]],INF,0);
            active.pop_front();
        }

        long long val=query(1,1,sz,pos[y[id]],sz,+1)-y[id];
        val=min(val,query(1,1,sz,1,pos[y[id]],0)+y[id]);

        if(i==inters.size()-1)
        {
            return 1LL*x[N-1]-1LL*x[0]+val+y[id];
        }

        update(1,1,sz,pos[y[id]],val+y[id],+1);
        update(1,1,sz,pos[y[id]],val-y[id],0);
    }
}

Compilation message (stderr)

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:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43