Submission #409777

#	Time	Username	Problem	Language	Result	Execution time	Memory
409777		MKopchev	Sky Walking (IOI19_walk)	C++14	43 / 100	2992 ms	230272 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>

using namespace std;

const int nmax=1e5+42;

set<int> there[nmax];
map<int,int> id[nmax];

vector<long long> dist;

vector< vector< pair<int,int> > > adj;

vector<int> inp;

void add_edge(int x1,int y1,int x2,int y2)
{
    int p=id[x1][y1];
    int q=id[x2][y2];

    int d=abs(inp[x1]-inp[x2])+abs(y1-y2);

    //cout<<"x1= "<<x1<<" y1= "<<y1<<" x2= "<<x2<<" y2= "<<y2<<" d= "<<d<<" p= "<<p<<" q= "<<q<<endl;

    while(adj.size()<=p)adj.push_back({});
    while(adj.size()<=q)adj.push_back({});

    adj[p].push_back({q,d});
    adj[q].push_back({p,d});
}

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

int tree[20][nmax];
int depth[nmax];

vector<int> mem_h,mem_l,mem_r,mem_y;

void build(int node,int l,int r)
{
    for(int step=0;(1<<step)<=r-l+1;step++)
    {
        for(int i=l;i+(1<<step)-1<=r;i++)
        {
            if(step==0)tree[step][i]=inp[i];
            else tree[step][i]=max(tree[step-1][i],tree[step-1][i+(1<<(step-1))]);
        }
    }
    depth[1]=0;
    for(int i=2;i<=r;i++)
        depth[i]=depth[i/2]+1;
}

void push(int i,int j)
{
    //cout<<"push "<<i<<" "<<j<<endl;

    if(mem_l[i]<=j&&j<=mem_r[i])
    {
        if(mem_h[j]>=mem_y[i])
        {
            //cout<<"in"<<endl;
            there[j].insert(mem_y[i]);
        }
    }
}
int query(int node,int l,int r,int lq,int rq)
{
    int d=depth[rq-lq+1];

    return max(tree[d][lq],tree[d][rq-(1<<d)+1]);
}

int get_first(int l,int r,int h)
{
    if(l>r)return -1;

    if(query(1,0,mem_h.size()-1,l,r)<h)return -1;

    int ok=r,not_ok=l-1;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        if(query(1,0,mem_h.size()-1,l,av)<h)not_ok=av;
        else ok=av;
    }
    return ok;
}

int get_last(int l,int r,int h)
{
    if(l>r)return -1;

    if(query(1,0,mem_h.size()-1,l,r)<h)return -1;

    int ok=l,not_ok=r+1;

    while(not_ok-ok>1)
    {
        int av=(ok+not_ok)/2;

        if(query(1,0,mem_h.size()-1,av,r)<h)not_ok=av;
        else ok=av;
    }
    return ok;
}

vector< pair<int,int> > updates[nmax];

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) {

    mem_l=l;
    mem_r=r;
    mem_y=y;

    if(s>g)swap(s,g);

    inp=x;
    mem_h=h;

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

	for(int i=0;i<x.size();i++)
        there[i].insert(0);

	for(int i=0;i<y.size();i++)
    {
        updates[l[i]].push_back({y[i],1});
        updates[r[i]+1].push_back({y[i],-1});

        //cout<<"line: "<<l[i]<<" "<<r[i]<<" "<<y[i]<<endl;

        /*
        for(int j=l[i];j<=r[i];j++)
            if(h[j]>=y[i])
            {
                //cout<<"push "<<j<<" h= "<<y[i]<<endl;

                there[j].insert(y[i]);
                noted[i].insert(j);
            }
        */

        push(i,l[i]);

        push(i,get_last(l[i],s,y[i]));

        push(i,get_first(s,g,y[i]));

        push(i,get_last(s,g,y[i]));

        push(i,get_first(g,r[i],y[i]));

        push(i,r[i]);
    }

    set<int> active={};
    map<int,int> cnt_active={};

    for(int i=0;i<x.size();i++)
    {
        for(auto w:updates[i])
        {
            cnt_active[w.first]+=w.second;

            active.erase(w.first);

            if(cnt_active[w.first])active.insert(w.first);
        }

        set<int> help=there[i];

        for(auto w:help)
        {
            set<int>::iterator it=active.lower_bound(w);

            if(it!=active.begin())
            {
                it--;

                int val=*it;

                if(0<=val&&val<=h[i])there[i].insert(val);

                //cout<<"low "<<*it<<endl;
            }

            it=active.upper_bound(w);

            if(it!=active.end())
            {
                int val=*it;

                if(0<=val&&val<=h[i])there[i].insert(val);

                //cout<<"high "<<*it<<endl;
            }
        }
    }

    int pointer=0;

    for(int i=0;i<x.size();i++)
    {
        for(auto w:there[i])
        {
            id[i][w]=pointer;

            //cout<<"id "<<i<<" "<<w<<" -> "<<pointer<<endl;

            pointer++;
        }
    }

    /*
    cout<<"towers: "<<endl;

    for(int i=0;i<x.size();i++)
    {
        cout<<"i= "<<i<<" : ";

        for(auto w:there[i])
            cout<<w<<" ";

        cout<<endl;
    }
    */

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

        for(auto w:there[i])
        {
            if(w)
            {
                add_edge(i,prv,i,w);
            }

            prv=w;
        }
    }

    //cout<<"-------------"<<endl;

    map<int, vector<int> > seen_by_y={};

    for(int i=0;i<x.size();i++)
    {
        for(auto w:there[i])
            seen_by_y[w].push_back(i);
    }

    map<int, vector< pair<int,int> > > seen_updates_y={};

    for(int i=0;i<y.size();i++)
        seen_updates_y[y[i]].push_back({l[i],r[i]});

    for(auto w:seen_by_y)
    {
        //cout<<l[i]<<" "<<r[i]<<" "<<y[i]<<" :"<<endl;

        vector<int> me=w.second;

        vector<int> pref=me;

        for(auto &t:pref)
            t=0;

        int prv=-1;

        for(auto u:seen_updates_y[w.first])
        {
            int p=lower_bound(me.begin(),me.end(),u.first)-me.begin();
            int q=lower_bound(me.begin(),me.end(),u.second)-me.begin();

            pref[p]++;
            pref[q]--;
        }

        for(int i=1;i<pref.size();i++)
            pref[i]+=pref[i-1];

        for(int i=0;i+1<pref.size();i++)
        {
            if(pref[i])
                add_edge(me[i],w.first,me[i+1],w.first);
        }
    }

    /*
    cout<<"there: "<<endl;
    for(int i=0;i<x.size();i++)
    {
        cout<<i<<" -> ";for(auto j:there[i])cout<<j<<" ";cout<<endl;
    }
    */

    for(int i=0;i<=pointer;i++)
        dist.push_back(-1);

    pq.push({0,id[s][0]});

    while(pq.size())
    {
        pair<long long,int> tp=pq.top();
        pq.pop();

        tp.first=-tp.first;

        if(dist[tp.second]!=-1)continue;

        dist[tp.second]=tp.first;

        //cout<<"dist: "<<tp.second<<" -> "<<tp.first<<endl;

        for(auto w:adj[tp.second])
            pq.push({-(tp.first+w.second),w.first});
    }

    return dist[id[g][0]];
}
/*
int main() {
    int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

Compilation message (stderr)

walk.cpp: In function 'void add_edge(int, int, int, int)':
walk.cpp:26:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     while(adj.size()<=p)adj.push_back({});
      |           ~~~~~~~~~~^~~
walk.cpp:27:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     while(adj.size()<=q)adj.push_back({});
      |           ~~~~~~~~~~^~~
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:126:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for(int i=0;i<x.size();i++)
      |              ~^~~~~~~~~
walk.cpp:129:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for(int i=0;i<y.size();i++)
      |              ~^~~~~~~~~
walk.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:206:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:232:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:251:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:259:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |     for(int i=0;i<y.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:284:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |         for(int i=1;i<pref.size();i++)
      |                     ~^~~~~~~~~~~~
walk.cpp:287:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  287 |         for(int i=0;i+1<pref.size();i++)
      |                     ~~~^~~~~~~~~~~~
walk.cpp:273:13: warning: unused variable 'prv' [-Wunused-variable]
  273 |         int prv=-1;
      |             ^~~

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