Submission #1226722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226722		eggx50000	Sky Walking (IOI19_walk)	C++20	57 / 100	1295 ms	148064 KiB

walk

#include "walk.h"
#include <set>
#include <iostream>
#include <vector>
#include <queue>
using ll = long long;
using namespace std;

int n, m;
int cn = 0;
struct Li{
    int l, r, h;
} ni[300099];
int na[100099][3];
int x[100099], h[100099], l[100099], r[100099], y[100099], s, g;
ll dst[300099][2];

struct HH{
    int nd, h;

    bool operator <(const HH &a) const{
        if(h == a.h) return nd < a.nd;
        else return h < a.h;
    }

};
set <HH> se;
vector <HH> pr[100099], de[100099];

struct Segt{
    int tr[400099];

    void build(int node, int s, int e){
        if(s == e){
            tr[node] = h[s];
            return;
        }
        int m = (s + e) / 2;
        build(node * 2, s, m);
        build(node * 2 + 1, m + 1, e);
        tr[node] = max(tr[node * 2], tr[node * 2 + 1]);
    }

    int qry(int node, int s, int e, int qs, int qe){
        if(qe < s || e < qs) return -1;
        if(qs <= s && e <= qe) return tr[node];
        int m = (s + e) / 2;
        return max(qry(node * 2, s, m, qs, qe), qry(node * 2 + 1, m + 1, e, qs, qe));
    }

} seg;

struct Ed{
    int u;
    ll v;

    bool operator <(const Ed &a) const{
        return v > a.v;
    }

};
vector <Ed> gr[300099], b[300099], ps[300099], pg[300099]; //g -> 불변, b -> 변

int fs(int l, int r, int v){ //[l, r] 구간에서 v이상인 원소의 최소 위치
    int s = l, e = r;
    while(s <= e){
        int m = (s + e) / 2;
        if(seg.qry(1, 1, n, l, m) >= v) e = m - 1;
        else s = m + 1;
    }
    return s;
}

int fe(int l, int r, int v){
    int s = l, e = r;
    while(s <= e){
        int m = (s + e) / 2;
        if(seg.qry(1, 1, n, m, r) >= v) s = m + 1;
        else e = m - 1;
    }
    return e;
}

void dijk(int t, int k){
    priority_queue <Ed> pq;
    for(int i = 1; i <= cn; i ++){
        if(ni[i].l == k || ni[i].r == k){
            pq.push({i, ni[i].h});
            dst[i][t] = ni[i].h;
        }
    }
    while(pq.size()){
        Ed to = pq.top();
        if(dst[to.u][t] > to.v) continue;
        pq.pop();
        for(Ed &e : gr[to.u]){
            if(dst[e.u][t] > e.v + to.v){
                dst[e.u][t] = e.v + to.v;
                pq.push({e.u, e.v + to.v});
            }
        }
        for(Ed &e : b[to.u]){
            if(e.u && dst[e.u][t] > e.v + to.v){
                dst[e.u][t] = e.v + to.v;
                pq.push({e.u, e.v + to.v});
            }
        }
    }
}

ll min_distance(vector<int> xin, vector<int> hin, vector<int> lin, vector<int> rin, vector<int> yin, int sin, int gin){
    n = xin.size(); m = lin.size();
    for(int i = 0; i < n; i ++) x[i + 1] = xin[i];
    for(int i = 0; i < n; i ++) h[i + 1] = hin[i];
    for(int i = 0; i < m; i ++) l[i + 1] = lin[i] + 1;
    for(int i = 0; i < m; i ++) r[i + 1] = rin[i] + 1;
    for(int i = 0; i < m; i ++) y[i + 1] = yin[i];
    s = sin + 1, g = gin + 1;
    if(s > g) swap(s, g);
    seg.build(1, 1, n);
    for(int i = 1; i <= m; i ++){
        int p, q;
        p = fs(l[i], min(s, r[i]), y[i]);
        q = fe(l[i], min(s, r[i]), y[i]);
        if(p <= q){
            ni[++cn] = {p, q, y[i]};
            na[i][0] = cn;
        }
        p = fs(max(s, l[i]), min(g, r[i]), y[i]);
        q = fe(max(s, l[i]), min(g, r[i]), y[i]);
        if(p <= q){
            ni[++cn] = {p, q, y[i]};
            na[i][1] = cn;
        }
        p = fs(max(l[i], g), r[i], y[i]);
        q = fe(max(l[i], g), r[i], y[i]);
        if(p <= q){
            ni[++cn] = {p, q, y[i]};
            na[i][2] = cn;
        }
    }
    for(int i = 1; i <= cn; i ++){
        pr[ni[i].l].push_back({i, ni[i].h});
        de[ni[i].r].push_back({i, ni[i].h});
    }
    for(int i = 1; i <= n; i ++){
        for(HH &e : pr[i]){
            auto it = se.lower_bound(e);
            if(it != se.end()){
                gr[it->nd].push_back({e.nd, it->h - e.h});
                gr[e.nd].push_back({it->nd, it->h - e.h});
            }
            if(it != se.begin()){
                it --;
                gr[it->nd].push_back({e.nd, e.h - it->h});
                gr[e.nd].push_back({it->nd, e.h - it->h});
            }
            se.insert(e);
        }
        for(HH &e : de[i]){
            auto it = se.lower_bound(e);
            it ++;
            bool fl = (it != se.end());
            it --;
            if(fl == true && it != se.begin()){
                it --;
                auto pit = it;
                it ++;
                it ++;
                auto ait = it;
                it --;
                gr[pit->nd].push_back({ait->nd, ait->h - pit->h});
                gr[ait->nd].push_back({pit->nd, ait->h - pit->h});
            }
            se.erase(e);
        }
    }
    for(int i = 0; i <= cn; i ++){
        for(int j = 0; j < 2; j ++){
            dst[i][j] = 1234567890123456789;
        }
    }

    for(int i = 1; i <= m; i ++){
        int p = na[i][0], q = na[i][1], r = na[i][2];
        ps[p].push_back({q, (x[s] - x[ni[p].r]) * 2});
        ps[p].push_back({r, (x[s] - x[ni[p].r]) * 2});
        ps[q].push_back({r, 0});
        ps[q].push_back({p, (x[ni[q].l] - x[s]) * 2});
        ps[r].push_back({p, (x[ni[r].l] - x[s]) * 2});
    }
    for(int i = 1; i <= m; i ++){
        int p = na[i][0], q = na[i][1], r = na[i][2];
        pg[r].push_back({q, (x[ni[r].l] - x[g]) * 2});
        pg[r].push_back({p, (x[ni[r].l] - x[g]) * 2});
        pg[q].push_back({p, 0});
        pg[q].push_back({r, (x[g] - x[ni[q].r]) * 2});
        pg[p].push_back({r, (x[g] - x[ni[p].r]) * 2});
    }
    for(int i = 1; i <= cn; i ++) b[i] = ps[i];
    dijk(0, s);
    for(int i = 1; i <= cn; i ++) b[i] = pg[i];
    dijk(1, g);
    ll mi = 1234567890123456789;
    for(int i = 1; i <= m; i ++){
        int p = na[i][0], q = na[i][1], r = na[i][2];
        if(p && q){
            mi = min(mi, dst[p][0] + dst[q][1] + x[g] - x[ni[p].r] + x[s] - x[ni[p].r]);
        }
        if(p && r){
            mi = min(mi, dst[p][0] + dst[r][1] + x[g] - x[ni[p].r] + x[s] - x[ni[p].r] + (x[ni[r].l] - x[g]) * 2);
        }
    }
    if(mi <= 1000000000000000000) return mi;
    else return -1;
}

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