제출 #296585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296585		humbertoyusta	Sky Walking (IOI19_walk)	C++14	10 / 100	4061 ms	369544 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << ": " << (x) << '\n';
#define f first
#define s second
#define pb push_back
#define ii pair<int,int>
#define ll long long
#define maxn 1000010
#define inf 1000000007
#define INF 1000000000000000000ll

ll dp[maxn];
priority_queue<pair<ll,int>> q;
int n, m;
ii imp[maxn];
int st[maxn*4];
vector<ii> G[maxn];
set<ii> S, S2;
map<ii,int> mp;
vector<pair<int,ii>> mp2;

void update(int nod,int l,int r,int id,int val){
    if( l == r ){ st[nod] = val; return; }
    int mi = ( l + r ) >> 1;
    if( id <= mi ) update(2*nod,l,mi,id,val);
        else update(2*nod+1,mi+1,r,id,val);
    st[nod] = max( st[2*nod] , st[2*nod+1] );
}

int query(int nod,int l,int r,int x,int y,int val){
    if( l > y || r < x || l > r ) return inf;
    if( l == r ){
        if( st[nod] >= val ) return l;
            else return inf;
    }
    int mi = ( l + r ) >> 1;
    if( l >= x && r <= y ){
        if( st[2*nod] >= val ) return query(2*nod,l,mi,x,y,val);
        if( st[2*nod+1] >= val ) return query(2*nod+1,mi+1,r,x,y,val);
        return inf;
    }
    return min( query(2*nod,l,mi,x,y,val) , query(2*nod+1,mi+1,r,x,y,val) );
}

void dijkstra(int start){
    fill( dp , dp + maxn , INF );
    q.push({0,start});
    dp[start] = 0;
    while( !q.empty() ){
        int u = q.top().s;
        q.pop();
        for( auto v : G[u] ){
            if( dp[v.f] > dp[u] + v.s ){
                dp[v.f] = dp[u] + v.s;
                q.push({-dp[v.f],v.f});
            }
        }
    }
}

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 = y.size();

    for(int i=0; i<n; i++){
        update(1,0,n-1,i,h[i]);
        S.insert((ii){x[i],h[i]});
        S.insert((ii){x[i],0});
    }

    for(int i=0; i<m; i++){
        int tl = l[i], tr = r[i];
        while( tl <= tr ){
            int p = query(1,0,n-1,tl,tr,y[i]);
            if( p == inf ) break;
            S.insert({x[p],y[i]});
            if( p > tl - 1 && tl - 1 >= l[i] ){ mp2.pb({y[i],{x[tl-1],x[p]}}); }
            tl = p + 1;
        }
    }

    int cnt = 0;
    for( auto i : S ){
        S2.insert({i.s,i.f});
        mp[{i.f,i.s}] = ++cnt;
    }

    for( auto i : S ){
        auto it = S.upper_bound(i);
        if( it != S.end() ){
            if( i.f == (*it).f ){//db(i.f)db(i.s)db((*it).f)db((*it).s)
                G[mp[i]].pb({mp[(*it)],abs((*it).s-i.s)});
                G[mp[(*it)]].pb({mp[i],abs((*it).s-i.s)});
            }
        }
    }

    for( auto i : mp2 ){
        int uf = i.s.f;
        int vf = i.s.s;
        int us = i.f;
        //cout<<mp[{uf,us}]<<'\n';
        //cout<<mp[{vf,us}]<<'\n';
        G[mp[{uf,us}]].pb({mp[{vf,us}],abs(vf-uf)});
        G[mp[{vf,us}]].pb({mp[{uf,us}],abs(vf-uf)});
    }

//    for( auto i : S2 ){
//        if( i.f == 0 ) continue;
//        auto it = S2.upper_bound(i);
//        if( it != S2.end() ){
//            if( i.f == (*it).f ){
//                int u = mp[{i.s,i.f}];
//                int v = mp[{(*it).s,(*it).f}];//db(i.s)db(i.f)db((*it).s)db((*it).f)
//                G[u].pb({v,abs((*it).s-i.s)});
//                G[v].pb({u,abs((*it).s-i.s)});
//            }
//        }
//    }

    dijkstra(mp[{x[s],0}]);
//    //cout<<dp[mp[{3,0}]]<<'\n';
//    //cout<<dp[mp[{3,1}]]<<'\n';
//    //cout<<dp[mp[{3,6}]]<<'\n';
//    //cout<<dp[mp[{5,6}]]<<'\n';
//    cout<<dp[mp[{5,7}]]<<'\n';
//    cout<<dp[mp[{14,7}]]<<'\n';
//    cout<<dp[mp[{14,5}]]<<'\n';
//    cout<<dp[mp[{12,5}]]<<'\n';
//    cout<<dp[mp[{12,0}]]<<'\n';

    if( dp[mp[{x[g],0}]] == INF ) return -1;
    return dp[mp[{x[g],0}]];
}

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