oj.uz

Submission #296746

# Submission time Handle Problem Language Result Execution time Memory
296746 2020-09-10T20:46:35 Z Leonardo16 Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 449888 KB 
#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);
#define f first
#define s second
#define pb push_back
#define ii pair<int,int>
#define ll long long
#define maxn 2000010
#define inf 1000000007
#define INF 1000000000000000000ll
/// 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[maxn];
priority_queue<pair<ll,int>> q;
int n, m;
int st[maxn*4];
vector<ii> G[maxn];
set<ii> S;
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,int emd){
    fill( dist , dist + maxn , INF );
    q.push({0,start});
    dist[start] = 0;
    while( !q.empty() ){
        int u = q.top().s;
        if( dist[u] < -q.top().f ){ q.pop(); continue; }
        q.pop();
        if( u == emd ) return;
        for( auto v : G[u] ){
            if( dist[v.f] > dist[u] + v.s ){
                dist[v.f] = dist[u] + v.s;
                q.push({-dist[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 ){
        mp[{i.f,i.s}] = ++cnt;
    }

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

    for( auto i : mp2 ){
        int uf = i.s.f;
        int vf = i.s.s;
        int us = i.f;
        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}]] == INF ) return -1;
    return dist[mp[{x[g],0}]];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62968 KB Output is correct
2 Correct 38 ms 62972 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 38 ms 62976 KB Output is correct
5 Correct 38 ms 63100 KB Output is correct
6 Correct 40 ms 63096 KB Output is correct
7 Correct 42 ms 63096 KB Output is correct
8 Correct 38 ms 62976 KB Output is correct
9 Correct 37 ms 62968 KB Output is correct
10 Correct 38 ms 63096 KB Output is correct
11 Correct 38 ms 62968 KB Output is correct
12 Correct 37 ms 62968 KB Output is correct
13 Correct 37 ms 62968 KB Output is correct
14 Correct 37 ms 62968 KB Output is correct
15 Correct 37 ms 62976 KB Output is correct
16 Correct 37 ms 62968 KB Output is correct
17 Correct 40 ms 63096 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62976 KB Output is correct
2 Correct 37 ms 62892 KB Output is correct
3 Correct 2377 ms 193888 KB Output is correct
4 Correct 2457 ms 223784 KB Output is correct
5 Correct 1920 ms 204680 KB Output is correct
6 Correct 1768 ms 189388 KB Output is correct
7 Correct 1952 ms 204716 KB Output is correct
8 Correct 3248 ms 229532 KB Output is correct
9 Correct 1988 ms 199580 KB Output is correct
10 Correct 3527 ms 276852 KB Output is correct
11 Correct 1255 ms 141612 KB Output is correct
12 Correct 933 ms 134332 KB Output is correct
13 Correct 3005 ms 253040 KB Output is correct
14 Correct 869 ms 125152 KB Output is correct
15 Correct 866 ms 118620 KB Output is correct
16 Correct 846 ms 118956 KB Output is correct
17 Correct 800 ms 117292 KB Output is correct
18 Correct 940 ms 136108 KB Output is correct
19 Correct 58 ms 65656 KB Output is correct
20 Correct 280 ms 90416 KB Output is correct
21 Correct 732 ms 114348 KB Output is correct
22 Correct 740 ms 118148 KB Output is correct
23 Correct 1042 ms 130736 KB Output is correct
24 Correct 828 ms 117852 KB Output is correct
25 Correct 791 ms 115884 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 76788 KB Output is correct
2 Execution timed out 4097 ms 449888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 76788 KB Output is correct
2 Execution timed out 4097 ms 449888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62968 KB Output is correct
2 Correct 38 ms 62972 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 38 ms 62976 KB Output is correct
5 Correct 38 ms 63100 KB Output is correct
6 Correct 40 ms 63096 KB Output is correct
7 Correct 42 ms 63096 KB Output is correct
8 Correct 38 ms 62976 KB Output is correct
9 Correct 37 ms 62968 KB Output is correct
10 Correct 38 ms 63096 KB Output is correct
11 Correct 38 ms 62968 KB Output is correct
12 Correct 37 ms 62968 KB Output is correct
13 Correct 37 ms 62968 KB Output is correct
14 Correct 37 ms 62968 KB Output is correct
15 Correct 37 ms 62976 KB Output is correct
16 Correct 37 ms 62968 KB Output is correct
17 Correct 40 ms 63096 KB Output is correct
18 Correct 37 ms 62976 KB Output is correct
19 Correct 37 ms 62892 KB Output is correct
20 Correct 2377 ms 193888 KB Output is correct
21 Correct 2457 ms 223784 KB Output is correct
22 Correct 1920 ms 204680 KB Output is correct
23 Correct 1768 ms 189388 KB Output is correct
24 Correct 1952 ms 204716 KB Output is correct
25 Correct 3248 ms 229532 KB Output is correct
26 Correct 1988 ms 199580 KB Output is correct
27 Correct 3527 ms 276852 KB Output is correct
28 Correct 1255 ms 141612 KB Output is correct
29 Correct 933 ms 134332 KB Output is correct
30 Correct 3005 ms 253040 KB Output is correct
31 Correct 869 ms 125152 KB Output is correct
32 Correct 866 ms 118620 KB Output is correct
33 Correct 846 ms 118956 KB Output is correct
34 Correct 800 ms 117292 KB Output is correct
35 Correct 940 ms 136108 KB Output is correct
36 Correct 58 ms 65656 KB Output is correct
37 Correct 280 ms 90416 KB Output is correct
38 Correct 732 ms 114348 KB Output is correct
39 Correct 740 ms 118148 KB Output is correct
40 Correct 1042 ms 130736 KB Output is correct
41 Correct 828 ms 117852 KB Output is correct
42 Correct 791 ms 115884 KB Output is correct
43 Correct 244 ms 76788 KB Output is correct
44 Execution timed out 4097 ms 449888 KB Time limit exceeded
45 Halted 0 ms 0 KB -