Submission #296182

#	Time	Username	Problem	Language	Result	Execution time	Memory
296182		Noam13	Sky Walking (IOI19_walk)	C++14	24 / 100	2183 ms	771576 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define loopr(i,s,e) for(int i=e-1;i>=s;--i)
#define chkmin(a,b) a = min(a,b)
#define chkmax(a,b) a = max(a,b)
using namespace std;
const int INF = 2e18;
struct SEG{
	int n, sz;
    vii a;
    SEG(vi& arr): n(arr.size()){
        for(sz=1;sz<n;sz*=2);
        a.resize(2*sz);
        loop(i,0,n) a[i+sz] = {arr[i],i};
        loopr(i,1,sz){
            a[i] = max(a[2*i], a[2*i+1]);
        }
    }
    ii query(int l, int r){
        ii best = {0, -1};
        for(l+=sz, r+=sz; l<=r; l/=2, r/=2){
            if (l%2) chkmax(best, a[l++]);
            if (r%2==0) chkmax(best, a[r--]);
        }
        return best;
    }
};
int n,m;
vvi inter;
vi h;
vvi vec;
void solve(SEG &seg, int a, int b, int x, int i){
    if (a>b) return ;
    ii v = seg.query(a,b);
    if (v.x < x) return ;
    inter[v.y].pb(x);
    vec[i].pb(v.y);
    solve(seg, a, v.y-1, x, i);
    solve(seg, v.y+1, b, x, i);
}
const int MAXN = 2e6 + 10;
long long min_distance(vector<int32_t> x, vector<int32_t> H, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t e) {
    n = x.size(), m = l.size();
    h.resize(n); loop(i,0,n) h[i] = H[i];
    SEG seg(h);
    inter.resize(n);
    vec.resize(m);
    loop(i,0,m){
        solve(seg, l[i], r[i], y[i], i);
        sort(all(vec[i]));
        //cout<<"SEG: "<<i<<" : ";
        //for(auto v:vec[i]) cout<<v<<" "; cout<<endl;
    }
    int cnt = 0;
    vii g[MAXN];
    loop(i,0,MAXN) g[i].clear();
    map<ii, int> conv;
    loop(i,0,n){
        inter[i].pb(0);
        sort(all(inter[i]));
        inter[i].resize(unique(all(inter[i]))-inter[i].begin());
        int last = -1;
        //cout<<"INTER: "<<i<<"  : ";
        for(auto x:inter[i]){
            //cout<<x<<endl;
            if (last!=-1){
                int dy = x - last;
                g[cnt].pb({cnt-1, dy});
                g[cnt-1].pb({cnt, dy});
            }
            conv[{i, x}] = cnt++;
            last = x;
        }
        //cout<<endl;
    }
    loop(i,0,m){
        int r = vec[i].size();
        loop(j,0,r-1){
            int a = vec[i][j], b = vec[i][j+1];
            int dx = abs(x[b] - x[a]);
            a = conv[{a, y[i]}], b = conv[{b, y[i]}];
            g[a].pb({b,dx});
            g[b].pb({a,dx});
        }
    }
    /*vii back(cnt);
    for(auto p:conv){
        //cout<<p.y<<" = "<< p.x.x<<", "<<p.x.y<<endl;
        back[p.y] = p.x;
    }*/
    s = conv[{s, 0}], e = conv[{e, 0}];
    vi dist(cnt, INF); dist[s] = 0;
    priority_queue<ii> q; q.push({0,s});
    while(q.size()){
        int cur =q.top().y, d = -q.top().x; q.pop();
        if (dist[cur]!=d) continue;
        if (cur==e) return d;
        //cout<<"cur: "<<cur<<" D="<<d<<" SZ="<<g[cur].size()<<endl;
        //cout<<"P: "<<back[cur].x<<" "<<back[cur].y<<endl;
        for(auto nei:g[cur]){
            if (dist[nei.x]>d + nei.y){
                dist[nei.x] = d + nei.y;
                q.push({-dist[nei.x], nei.x});
            }
        }
    }
	return -1;
}
/*
clear
g++ grader.cpp walk2.cpp -o a ; ./a
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5


*/

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