Submission #296737

#	Time	Username	Problem	Language	Result	Execution time	Memory
296737		Leonardo16	Sky Walking (IOI19_walk)	C++14	0 / 100	112 ms	21040 KiB

walk

#include<bits/stdc++.h>
#include "walk.h"
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("avx2")
//#define int  long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define fst first
#define scd second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
/// Functions
#define db(x) cerr << #x << ": " << (x) << '\n';
#define random() __builtin_ia32_rdtsc()
#define lg2(x) 31-__builtin_clz(x)
#define lg2ll(x) 63-__builtin_clzll(x)
#define pi acos(-1)
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
#define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;}
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
/// Red-Black Tree Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
//#define less_than(n) order_of_key(n)
//#define en_pos(n) find_by_order(n)
/// Prime numbers  173,179,311,331,737,1009,2011,2027,3079,4001,100003
///=====================================================================
ll dist[2000005];
priority_queue<pair<ll,int>> q;
vector<pair<int,ii>> mp2;
int n, m;
set<ii> S;
map<ii,int> mp;
int st[8000005];
vii G[000005];

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 1e18;
    if( l == r ){
        if( st[nod] >= val ) return l;
            else return 1e18;
    }
    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 1e18;
    }
    return min( query(2*nod,l,mi,x,y,val) , query(2*nod+1,mi+1,r,x,y,val) );
}

void dijkstra(int start,int emd){
    fill(dist,dist+200005,1e18);
    q.push({0,start});
    dist[start] = 0;
    while( !q.empty() ){
        int u = q.top().scd;
        if( dist[u] < -q.top().fst ){ q.pop(); continue; }
        q.pop();
        if( u == emd ) return;
        for( auto v : G[u] ){
            if( dist[v.fst] > dist[u] + v.scd ){
                dist[v.fst] = dist[u] + v.scd;
                q.push({-dist[v.fst],v.fst});
            }
        }
    }
}



ll min_distance(vi x, vi h, vi l, vi r, vi 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 == 1e18 ) 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 ){mp[{i.fst,i.scd}] = ++cnt;}

    for( auto i : S ){
        auto it = S.upper_bound(i);
        if( it == S.end() ) continue;
        ii j = *it;
        if( i.fst == j.fst ){
            int u = mp[i];
            int v = mp[j];
            G[u].pb({v,abs(j.scd-i.scd)});
            G[v].pb({u,abs(j.scd-i.scd)});
        }
    }

    for( auto i : mp2 ){
        int uf = i.scd.fst;
        int vf = i.scd.scd;
        int us = i.fst;
        int u = mp[{uf,us}];
        int v = mp[{vf,us}];
        G[u].pb({v,abs(uf-vf)});
        G[v].pb({u,abs(uf-vf)});
    }
    dijkstra(mp[{x[s],0}],mp[{x[g],0}]);
    if( dist[mp[{x[g],0}]] == 1e18 ) return -1;
    return dist[mp[{x[g],0}]];
}

Compilation message (stderr)

walk.cpp: In function 'int query(int, int, int, int, int, int)':
walk.cpp:60:42: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   60 |     if( l > y || r < x || l > r ) return 1e18;
      |                                          ^~~~
walk.cpp:63:25: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   63 |             else return 1e18;
      |                         ^~~~
walk.cpp:69:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   69 |         return 1e18;
      |                ^~~~

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