제출 #874243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874243		andrei_boaca	Sky Walking (IOI19_walk)	C++17	10 / 100	118 ms	65852 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;
int n,m;
int ind;
vector<pii> muchii[1000005];
vector<pii> nodes[1000005];
vector<int> where[100005];
int arb[4*100005],toprop[4*100005];
ll dp[100005];
struct skywalk
{
    ll l,r,h,ind;
} v[100005];
ll dist[1000005];
bool comp(pii a,pii b)
{
    return a.second<b.second;
}
bool cresc(skywalk a, skywalk b)
{
    if(a.h!=b.h)
        return a.h<b.h;
    return a.l>b.l;
}
bool byr(skywalk a, skywalk b)
{
    return a.r<b.r;
}
bool descresc(skywalk a, skywalk b)
{
    if(a.h!=b.h)
        return a.h>b.h;
    return a.l>b.l;
}
void addnode(int x,int y)
{
    ind++;
    nodes[x].push_back({y,ind});
}
bool use[2000005];
void bfs()
{
    for(int i=1;i<=ind;i++)
        dist[i]=INF;
    dist[1]=0;
    priority_queue<pll,vector<pll>, greater<pll>> pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        int nod=pq.top().second;
        if(nod==2)
            return;
        pq.pop();
        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;
                pq.push({dist[i.first],i.first});
            }
    }
}
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)
{
    n=x.size();
    m=l.size();
    if(x.size()<=50&&l.size()<=50)
    {
        addnode(s,0);
        addnode(g,0);
        for(int i=0;i<l.size();i++)
        {
            int prv=-1;
            for(int j=l[i];j<=r[i];j++)
                if(y[i]<=h[j])
                {
                    addnode(j,y[i]);
                    if(prv!=-1)
                    {
                        int a=ind-1;
                        int b=ind;
                        muchii[a].push_back({b,x[j]-x[prv]});
                        muchii[b].push_back({a,x[j]-x[prv]});
                    }
                    prv=j;
                }
        }
        for(int i=0;i<n;i++)
            if(!nodes[i].empty())
            {
                sort(nodes[i].begin(),nodes[i].end());
                for(int j=1;j<nodes[i].size();j++)
                {
                    ll d=nodes[i][j].first-nodes[i][j-1].first;
                    ll a=nodes[i][j].second;
                    ll b=nodes[i][j-1].second;
                    muchii[a].push_back({b,d});
                    muchii[b].push_back({a,d});
                }
            }
        bfs();
        if(dist[2]==INF)
            return -1;
        return dist[2];
    }
    for(int i=0;i<m;i++)
        v[i]={l[i],r[i],y[i],i};
    sort(v,v+m,cresc);
    build(1,0,n-1);
    for(int i=0;i<m;i++)
    {
        int rgt=v[i].r;
        int val=query(1,0,n-1,rgt);
        if(val!=-1)
            where[v[i].ind].push_back(val);
        update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
    }
    sort(v,v+m,descresc);
    build(1,0,n-1);
    for(int i=0;i<m;i++)
    {
        int rgt=v[i].r;
        int val=query(1,0,n-1,rgt);
        if(val!=-1)
            where[v[i].ind].push_back(val);
        update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
    }
    ll ans=INF;
    sort(v,v+m,byr);
    for(int i=0;i<m;i++)
        dp[i]=INF;
    for(int i=0;i<m;i++)
    {
        ll ind=v[i].ind;
        if(v[i].l==0)
            dp[ind]=min(dp[ind],v[i].h);
        if(v[i].r==n-1)
            ans=min(ans,dp[ind]+v[i].h+x[n-1]-x[0]);
        for(int j:where[ind])
            dp[j]=min(dp[j],dp[ind]+abs(y[j]-y[ind]));
    }
    if(ans==INF)
        return -1;
    return ans;
}

컴파일 시 표준 에러 (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:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int i=0;i<l.size();i++)
      |                     ~^~~~~~~~~
walk.cpp:151:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |                 for(int j=1;j<nodes[i].size();j++)
      |                             ~^~~~~~~~~~~~~~~~

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