Submission #286377

#	Time	Username	Problem	Language	Result	Execution time	Memory
286377		MKopchev	Sky Walking (IOI19_walk)	C++14	10 / 100	3116 ms	297600 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

const long long inf=1e18;

map< pair<int,int>, vector< pair<int,int> > >edges;

map< pair<int,int>,long long> mem;

set<int> seen[nmax];

priority_queue< pair<long long,pair<int,int> > > pq;

vector<int> mem_x,mem_h;

int dist(pair<int,int> a,pair<int,int> b)
{
    return abs(mem_x[a.first]-mem_x[b.first])+abs(a.second-b.second);
}

int stop=0;

void dij(pair<int,int> start)
{
    pq.push({0,start});

    while(pq.size()&&mem.count({stop,0})==0)
    {
        pair<long long,pair<int,int> > tp=pq.top();
        pq.pop();

        if(mem.count(tp.second))continue;

        tp.first=-tp.first;

        mem[tp.second]=tp.first;

        //cout<<tp.first<<" "<<tp.second.first<<" "<<tp.second.second<<endl;

        for(auto k:edges[tp.second])
            pq.push({-(dist(k,tp.second)+tp.first),k});
    }
}

vector< pair<int,int> > tree[4*nmax];

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].push_back({mem_h[l],l});
        return;
    }

    int av=(l+r)/2;

    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=tree[node*2];

    for(auto k:tree[node*2+1])
        tree[node].push_back(k);

    sort(tree[node].begin(),tree[node].end());
}

vector<int> given;

void query(int node,int l,int r,int lq,int rq,int low)
{
    if(l==lq&&r==rq)
    {
        int pointer=tree[node].size()-1;

        while(pointer>=0&&tree[node][pointer].first>=low)
        {
            given.push_back(tree[node][pointer].second);
            pointer--;
        }
        return;
    }
    int av=(l+r)/2;

    if(lq<=av)query(node*2,l,av,lq,min(av,rq),low);
    if(av<rq)query(node*2+1,av+1,r,max(av+1,lq),rq,low);
}

vector< int/*h*/> to_push[nmax],to_pop[nmax];

set< pair<int/*h*/,long long/*value*/> > active;

long long special(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
    for(int i=0;i<l.size();i++)
    {
        to_push[l[i]].push_back(y[i]);
        to_pop[r[i]].push_back(y[i]);
    }

    for(int i=0;i<x.size();i++)
    {
        sort(to_push[i].begin(),to_push[i].end());
        sort(to_pop[i].begin(),to_pop[i].end());
    }

    active.insert({0,0});

    long long mini=1e18;

    for(int i=0;i<x.size();i++)
    {
        for(auto k:to_push[i])
        {
            long long mini=inf;

            set< pair<int/*h*/,long long/*value*/> >::iterator it=active.lower_bound({k,0});

            if(it!=active.end())
            {
                if((*it).first==k)continue;
            }

            if(it!=active.end())
            {
                mini=min(mini,(*it).second+abs(k-(*it).first));
            }

            if(it!=active.begin())
            {
                it--;
                mini=min(mini,(*it).second+abs(k-(*it).first));
            }

            active.insert({k,mini});
        }

        for(auto k:to_pop[i])
        {
            set< pair<int/*h*/,long long/*value*/> >::iterator it=active.lower_bound({k,0});

            if(i==x.size()-1)
            {
                mini=min(mini,(*it).first+(*it).second);
            }

            active.erase(*it);
        }

        if(i==0)active.erase({0,0});

        if(i!=x.size()-1&&active.size()==0)return -1;
        /*
        cout<<i<<" -> "<<endl;
        for(auto k:active)
            cout<<k.first<<" "<<k.second<<endl;
        cout<<"---"<<endl;
        */
    }

    for(auto k:active)
        mini=min(mini,k.first+k.second);

    mini=mini+x[x.size()-1]-x[0];

    return mini;
}

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)
{
    if(s==0&&g==x.size()-1)return special(x,h,l,r,y,s,g);

    stop=g;

    mem_x=x;
    mem_h=h;

    build(1,0,x.size()-1);

    for(int t=0;t<l.size();t++)
    {
        int prv=-1;

        given={};

        query(1,0,x.size()-1,l[t],r[t],y[t]);

        sort(given.begin(),given.end());

        for(auto j:given)
            if(h[j]>=y[t])
            {
                seen[j].insert(y[t]);

                if(prv!=-1)
                {
                    edges[{j,y[t]}].push_back({prv,y[t]});
                    edges[{prv,y[t]}].push_back({j,y[t]});
                }

                prv=j;
            }
    }

    seen[s].insert(0);
    seen[g].insert(0);

    for(int i=0;i<x.size();i++)
    {
        int prv=-1;

        for(auto k:seen[i])
        {
            if(prv!=-1)
            {
                edges[{i,prv}].push_back({i,k});
                edges[{i,k}].push_back({i,prv});
            }

            prv=k;
        }
    }

    dij({s,0});

    if(mem.count({g,0}))return mem[{g,0}];
    return -1;
}

Compilation message (stderr)

walk.cpp: In function 'long long int special(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:145:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |             if(i==x.size()-1)
      |                ~^~~~~~~~~~~~
walk.cpp:155:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         if(i!=x.size()-1&&active.size()==0)return -1;
      |            ~^~~~~~~~~~~~
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:174:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     if(s==0&&g==x.size()-1)return special(x,h,l,r,y,s,g);
      |              ~^~~~~~~~~~~~
walk.cpp:183:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int t=0;t<l.size();t++)
      |                 ~^~~~~~~~~
walk.cpp:211:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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