oj.uz

Submission #296599

# Submission time Handle Problem Language Result Execution time Memory
296599 2020-09-10T16:58:44 Z humbertoyusta Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 449096 KB 
#include "walk.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 2000010
#define inf 1000000007
#define INF 1000000000000000000ll

ll dp[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 end_){
    fill( dp , dp + maxn , INF );
    q.push({0,start});
    dp[start] = 0;
    while( !q.empty() ){
        int u = q.top().s;
        if( dp[u] < -q.top().f ){ q.pop(); continue; }
        q.pop();
        if( u == end_ ) return;
        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() ) 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( dp[mp[{x[g],0}]] == INF ) return -1;
    return dp[mp[{x[g],0}]];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62976 KB Output is correct
2 Correct 40 ms 62972 KB Output is correct
3 Correct 40 ms 62968 KB Output is correct
4 Correct 40 ms 62976 KB Output is correct
5 Correct 42 ms 63128 KB Output is correct
6 Correct 41 ms 63096 KB Output is correct
7 Correct 40 ms 62992 KB Output is correct
8 Correct 40 ms 62976 KB Output is correct
9 Correct 40 ms 62976 KB Output is correct
10 Correct 42 ms 63104 KB Output is correct
11 Correct 44 ms 63232 KB Output is correct
12 Correct 45 ms 62968 KB Output is correct
13 Correct 40 ms 62968 KB Output is correct
14 Correct 41 ms 62968 KB Output is correct
15 Correct 41 ms 62976 KB Output is correct
16 Correct 41 ms 62976 KB Output is correct
17 Correct 46 ms 63116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62968 KB Output is correct
2 Correct 40 ms 63104 KB Output is correct
3 Correct 2422 ms 191712 KB Output is correct
4 Correct 2517 ms 219516 KB Output is correct
5 Correct 1989 ms 201060 KB Output is correct
6 Correct 1784 ms 185892 KB Output is correct
7 Correct 1954 ms 201116 KB Output is correct
8 Correct 3209 ms 227172 KB Output is correct
9 Correct 2032 ms 196040 KB Output is correct
10 Correct 3627 ms 272996 KB Output is correct
11 Correct 1260 ms 141572 KB Output is correct
12 Correct 957 ms 134316 KB Output is correct
13 Correct 2991 ms 252972 KB Output is correct
14 Correct 883 ms 125100 KB Output is correct
15 Correct 841 ms 118444 KB Output is correct
16 Correct 857 ms 118828 KB Output is correct
17 Correct 811 ms 117164 KB Output is correct
18 Correct 981 ms 135980 KB Output is correct
19 Correct 59 ms 65656 KB Output is correct
20 Correct 297 ms 90320 KB Output is correct
21 Correct 749 ms 114328 KB Output is correct
22 Correct 721 ms 118060 KB Output is correct
23 Correct 1042 ms 130528 KB Output is correct
24 Correct 786 ms 117936 KB Output is correct
25 Correct 788 ms 116012 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 76592 KB Output is correct
2 Execution timed out 4091 ms 449096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 76592 KB Output is correct
2 Execution timed out 4091 ms 449096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62976 KB Output is correct
2 Correct 40 ms 62972 KB Output is correct
3 Correct 40 ms 62968 KB Output is correct
4 Correct 40 ms 62976 KB Output is correct
5 Correct 42 ms 63128 KB Output is correct
6 Correct 41 ms 63096 KB Output is correct
7 Correct 40 ms 62992 KB Output is correct
8 Correct 40 ms 62976 KB Output is correct
9 Correct 40 ms 62976 KB Output is correct
10 Correct 42 ms 63104 KB Output is correct
11 Correct 44 ms 63232 KB Output is correct
12 Correct 45 ms 62968 KB Output is correct
13 Correct 40 ms 62968 KB Output is correct
14 Correct 41 ms 62968 KB Output is correct
15 Correct 41 ms 62976 KB Output is correct
16 Correct 41 ms 62976 KB Output is correct
17 Correct 46 ms 63116 KB Output is correct
18 Correct 41 ms 62968 KB Output is correct
19 Correct 40 ms 63104 KB Output is correct
20 Correct 2422 ms 191712 KB Output is correct
21 Correct 2517 ms 219516 KB Output is correct
22 Correct 1989 ms 201060 KB Output is correct
23 Correct 1784 ms 185892 KB Output is correct
24 Correct 1954 ms 201116 KB Output is correct
25 Correct 3209 ms 227172 KB Output is correct
26 Correct 2032 ms 196040 KB Output is correct
27 Correct 3627 ms 272996 KB Output is correct
28 Correct 1260 ms 141572 KB Output is correct
29 Correct 957 ms 134316 KB Output is correct
30 Correct 2991 ms 252972 KB Output is correct
31 Correct 883 ms 125100 KB Output is correct
32 Correct 841 ms 118444 KB Output is correct
33 Correct 857 ms 118828 KB Output is correct
34 Correct 811 ms 117164 KB Output is correct
35 Correct 981 ms 135980 KB Output is correct
36 Correct 59 ms 65656 KB Output is correct
37 Correct 297 ms 90320 KB Output is correct
38 Correct 749 ms 114328 KB Output is correct
39 Correct 721 ms 118060 KB Output is correct
40 Correct 1042 ms 130528 KB Output is correct
41 Correct 786 ms 117936 KB Output is correct
42 Correct 788 ms 116012 KB Output is correct
43 Correct 235 ms 76592 KB Output is correct
44 Execution timed out 4091 ms 449096 KB Time limit exceeded
45 Halted 0 ms 0 KB -