Submission #874351

#	Time	Username	Problem	Language	Result	Execution time	Memory
874351		andrei_boaca	Sky Walking (IOI19_walk)	C++17	100 / 100	3125 ms	257576 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
map<pii,int> f;
int cnt;
vector<pii> muchii[3000005];
vector<pii> nodes;
vector<int> whovert[100005],whooriz[100005];
int arb[4*100005],toprop[4*100005];
int n,m;
struct skywalk
{
    ll l,r,h,ind;
} v[100005];
vector<int> X,H,L,R,Y;
bool Hdesc(int a,int b)
{
    return H[a]>H[b];
}
bool Hcresc(skywalk a, skywalk b)
{
    return a.h<b.h;
}
void addnode(int i,int j)
{
    //cout<<X[i]<<' '<<Y[j]<<'\n';
    cnt++;
    f[{X[i],Y[j]}]=cnt;
    nodes.push_back({i,j});
    whovert[i].push_back(Y[j]);
    whooriz[j].push_back(X[i]);
}
bool cresc(pii a,pii b)
{
    return Y[a.second]<Y[b.second];
}
bool use[3000005];
ll dist[3000005];
ll bfs(ll s,ll g)
{
    priority_queue<pll,vector<pll>,greater<pll>> coada;
    for(int i=1;i<=cnt;i++)
    {
        dist[i]=INF;
        if(nodes[i].first==s)
        {
            dist[i]=Y[nodes[i].second];
            coada.push({dist[i],i});
        }
    }
    ll ans=INF;
    while(!coada.empty())
    {
        int nod=coada.top().second;
        coada.pop();
        if(nodes[nod].first==g)
            ans=min(ans,dist[nod]+Y[nodes[nod].second]);
        if(use[nod])
            continue;
        use[nod]=1;
        for(auto i:muchii[nod])
            if(dist[i.first]>dist[nod]+i.second)
            {
                dist[i.first]=dist[nod]+i.second;
                coada.push({dist[i.first],i.first});
            }
    }
    if(ans==INF)
        return -1;
    return ans;
}
void prop(int nod)
{
    int val=toprop[nod];
    arb[nod*2]=val;
    arb[nod*2+1]=val;
    toprop[nod*2]=val;
    toprop[nod*2+1]=val;
}
void build(int nod,int st,int dr)
{
    arb[nod]=-1;
    toprop[nod]=-1;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st>=a&&dr<=b)
    {
        arb[nod]=val;
        toprop[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
}
int query(int nod,int st,int dr,int poz)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st==dr)
        return arb[nod];
    int mij=(st+dr)/2;
    if(poz<=mij)
        return query(nod*2,st,mij,poz);
    else
        return query(nod*2+1,mij+1,dr,poz);
}
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)
{
    X=x;
    H=h;
    L=l;
    R=r;
    Y=y;
    n=x.size();
    m=l.size();
    nodes.push_back({0,0});
    for(int i=0;i<m;i++)
        v[i]={l[i],r[i],y[i],i};
    vector<int> ups;
    for(int i=0;i<n;i++)
        ups.push_back(i);
    sort(ups.begin(),ups.end(),Hdesc);
    sort(v,v+m,Hcresc);
    set<int> setik;
    for(int i=0;i<n;i++)
        setik.insert(i);
    for(int i=0;i<m;i++)
    {
        while(!ups.empty()&&H[ups.back()]<v[i].h)
        {
            setik.erase(ups.back());
            ups.pop_back();
        }
        addnode(v[i].l,v[i].ind);
        addnode(v[i].r,v[i].ind);
        if(setik.find(s)!=setik.end())
        {
            if(s>=v[i].l&&s<=v[i].r)
                addnode(s,v[i].ind);
        }
        else
        {
            auto it=setik.lower_bound(s);
            if(it!=setik.end())
            {
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
            if(it!=setik.begin())
            {
                it=prev(it);
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
        }
        if(setik.find(g)!=setik.end())
        {
            if(g>=v[i].l&&g<=v[i].r)
                addnode(g,v[i].ind);
        }
        else
        {
            auto it=setik.lower_bound(g);
            if(it!=setik.end())
            {
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
            if(it!=setik.begin())
            {
                it=prev(it);
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
        }
    }
    vector<pii> ord=nodes;
    sort(ord.begin(),ord.end(),cresc);
    build(1,0,n-1);
    int poz=0;
    for(auto i:ord)
    {
        while(poz<m&&v[poz].h<Y[i.second])
        {
            update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
            poz++;
        }
        int val=query(1,0,n-1,i.first);
        if(val!=-1)
        {
            if(Y[val]<=H[i.first])
                addnode(i.first,val);
        }
    }

    reverse(ord.begin(),ord.end());
    reverse(v,v+m);
    build(1,0,n-1);
    poz=0;
    for(auto i:ord)
    {
        while(poz<m&&v[poz].h>Y[i.second])
        {
            update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
            poz++;
        }
        int val=query(1,0,n-1,i.first);
        if(val!=-1)
        {
            if(Y[val]<=H[i.first])
                addnode(i.first,val);
        }
    }

    for(int i=0;i<n;i++)
    {
        sort(whovert[i].begin(),whovert[i].end());
        for(int j=1;j<whovert[i].size();j++)
        {
            int ya=whovert[i][j-1];
            int yb=whovert[i][j];
            int a=f[{X[i],ya}];
            int b=f[{X[i],yb}];
            muchii[a].push_back({b,yb-ya});
            muchii[b].push_back({a,yb-ya});
        }
    }

    for(int i=0;i<m;i++)
    {
        sort(whooriz[i].begin(),whooriz[i].end());
        for(int j=1;j<whooriz[i].size();j++)
        {
            int xa=whooriz[i][j-1];
            int xb=whooriz[i][j];
            int a=f[{xa,Y[i]}];
            int b=f[{xb,Y[i]}];
            muchii[a].push_back({b,xb-xa});
            muchii[b].push_back({a,xb-xa});
        }
    }
    return bfs(s,g);
}

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:239:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         for(int j=1;j<whovert[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~
walk.cpp:253:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |         for(int j=1;j<whooriz[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~

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