제출 #286716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286716		CaroLinda	Sky Walking (IOI19_walk)	C++14	0 / 100	55 ms	10800 KiB

walk

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

#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>

const int MAXN = 1e5+100 ;
const int inf = 1e9+7 ;
const ll linf = 1e18+10 ;

using namespace std ;

struct Seg
{

    vector<int> y ;
    int id[MAXN*4] , mx[MAXN*4] ;

    int m(int l, int r) { return (l+r)>>1 ; }
    void upd(int pos, int l, int r, int beg, int en , int k )
    {

        if( l > en || r < beg ) return ;

        mx[pos] = k ;

        if(l >= beg && r <= en)
        {
            id[pos] = k ;
            return ;
        }

        upd(pos<<1 , l, m(l,r) , beg, en, k ) ;
        upd(pos<<1|1 , m(l,r) + 1 , r , beg, en ,k ) ;

    }
    int qry(int pos, int l, int r, int beg, int en)
    {

        if( l > en || r < beg ) return sz(y)-1 ;
        if( l >= beg && r <= en ) return mx[pos] ;

        int al = qry(pos<<1 , l, m(l,r) , beg, en ) ;
        int ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;

        if( y[ id[pos] ] <= min( y[ al ] , y[ar] ) ) return id[pos] ;

        return y[al] < y[ar] ? al : ar ;

    }

} seg ;

struct Event
{
    int y , l , r , id ;

    Event(int y = 0 ,int l = 0 , int r = 0 , int id = 0 ) : y(y) , l(l) , r(r) , id(id) {}

    bool operator < ( Event other ) const { return y > other.y ; }

};

int N , M , S , G ;
vector<Event> sweep ;
vector<pii> adj[MAXN] ;
ll dist[MAXN] ;

void dijkstra()
{
    lp(i,0,M) dist[i] = linf ;
    dist[M-2] = 0 ;

    priority_queue< pair<ll,int> , vector<pair<ll,int> > , greater< pair<ll,int> > > fila ;
    fila.push(mk(0,M-2)) ;

    while(!fila.empty())
    {
        int x = fila.top().ss ;
        ll d = fila.top().ff ;

        fila.pop() ;

        if(d != dist[x]) continue ;

        for(auto e : adj[x] )
        {
            ll dd = d + (ll)e.ss ;
            if(dd >= dist[e.ff]) continue ;

            fila.push( mk( (dist[e.ff] = dd) , e.ff ) ) ;

        }

    }

}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{

    if(s == g) return 0LL ;

    N = sz(x) ;
    l.pb(0) ;
    r.pb(0) ;
    y.pb(0) ;
    l.pb( N-1 ) ;
    r.pb(N-1) ;
    y.pb(0) ;
    M = sz(l) ;
    S = s ;
    G = g ;

    lp(i,0,M)
    {
        sweep.pb( Event( y[i] , l[i] , r[i] , i) ) ;
        seg.y.pb( y[i] ) ;
    }
    seg.y.pb( inf ) ;
    lp(i,0,MAXN*4) seg.id[i] = seg.mx[i]= sz(seg.y) - 1 ;

    sort(all(sweep)) ;

    for(auto e : sweep )
    {

       // debug("Processing %d %d %d\n" , e.y , e.l , e.r ) ;

        int mnY = seg.qry( 1 , 1 , N , e.l + 1 , e.r+1 ) ;
        seg.upd(1,1,N, e.l + 1 ,e.r + 1 , e.id ) ;

        //debug("E deu %d\n\n" , mnY ) ;

        if( mnY == sz(y) ) continue ;

        adj[ mnY ].pb( mk( e.id , y[mnY] - y[e.id] ) ) ;
        adj[e.id].pb( mk( mnY , y[mnY] - y[e.id] ) ) ;

    }

   /* lp(i,0,M)
    {
        debug("Adjacency of %d (%d %d %d):\n", i , l[i] , r[i] , y[i] ) ;
        for(auto e : adj[i]) debug("%d %d\n" , e.ff, e.ss ) ;
        debug("\n") ;
    } */

    dijkstra() ;

    if( dist[M-1] == linf ) return -1 ;

    return x[N-1] - x[0] + dist[M-1] ;

}

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