Submission #222649

#	Time	Username	Problem	Language	Result	Execution time	Memory
222649		VEGAnn	Sky Walking (IOI19_walk)	C++14	57 / 100	4103 ms	511252 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const ll OO = 1e18;
unordered_map<int, int> MEM[N];
set<array<ll, 3> > pq;
vector<ll> Ans[N];
vector<int> vc, real_y, tch[N], tct[N];
vector<array<int, 3> > lines;
vector<pii> events[N];
int n, m, pos, H[N], nm[N], Y[N];
bool fd;
ll st[4 * N], psh[4 * N], ans = OO, gt_vl, bad;

void build(int v, int l, int r){
    psh[v] = 0;
    st[v] = OO;

    if (l == r) return;

    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);
}

void bluid(int v, int l, int r){
    if (l == r){
        st[v] = -H[l];
        return;
    }

    int md = (l + r) >> 1;

    bluid(v + v, l, md);
    bluid(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void push(int v){
    if (psh[v] != 0){
        st[v] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void update(int v, int l, int r, int ps, ll vl){
    push(v);

    if (l == r){
        st[v] = vl;
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps, vl);
    else update(v + v + 1, md + 1, r, ps, vl);

    push(v + v);
    push(v + v + 1);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void add(int v, int tl, int tr, int l, int r, ll vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r){
        psh[v] += vl;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;
    add(v + v, tl, md, l, min(r, md), vl);
    add(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void real_search_left(int v, int l, int r){
    push(v);

    if (l == r){
        fd = 1;
        pos = l;
        gt_vl = st[v];
        return;
    }

    push(v + v);
    push(v + v + 1);

    int md = (l + r) >> 1;

    if (st[v + v + 1] < bad)
        real_search_left(v + v + 1, md + 1, r);
    else real_search_left(v + v, l, md);
}

void search_left(int v, int tl, int tr, int l, int r){
    push(v);

    if (fd || l > r) return;

    if (tl == l && tr == r){
        if (st[v] < bad)
            real_search_left(v, l, r);
        return;
    }

    int md = (tl + tr) >> 1;
    search_left(v + v + 1, md + 1, tr, max(md + 1, l), r);
    search_left(v + v, tl, md, l, min(r, md));
}


void real_search_right(int v, int l, int r){
    push(v);

    if (l == r){
        fd = 1;
        pos = l;
        gt_vl = st[v];
        return;
    }

    push(v + v);
    push(v + v + 1);

    int md = (l + r) >> 1;

    if (st[v + v] < bad)
        real_search_right(v + v, l, md);
    else real_search_right(v + v + 1, md + 1, r);
}

void search_right(int v, int tl, int tr, int l, int r){
    push(v);

    if (fd || l > r) return;

    if (tl == l && tr == r){
        if (st[v] < bad)
            real_search_right(v, l, r);
        return;
    }

    int md = (tl + tr) >> 1;
    search_right(v + v, tl, md, l, min(r, md));
    search_right(v + v + 1, md + 1, tr, max(md + 1, l), r);
}

void get_ans(int v, int l, int r){
    push(v);
    if (l == r){
        if (st[v] < OO)
            ans = min(ans, st[v] + ll(real_y[l]));
        return;
    }

    int md = (l + r) >> 1;
    get_ans(v + v, l, md);
    get_ans(v + v + 1, md + 1, r);
}

bool cmp(int _x, int _y){
    return Y[_x] < Y[_y];
}

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) {
    lines.clear();

    n = sz(x); m = sz(l);

    for (int i = 0; i < m; i++) {
        real_y.PB(y[i]);
        nm[i] = i;
        Y[i] = y[i];
    }

    sort(all(real_y));
    real_y.resize(unique(all(real_y)) - real_y.begin());

    for (int i = 0; i < m; i++){
        y[i] = lower_bound(all(real_y), y[i]) - real_y.begin();
    }

    if (s != 0 || g != n - 1){
//    if (1){
        for (int i = 0; i < n; i++)
            H[i] = h[i];

        bluid(1, 0, n - 1);

        sort(nm, nm + m, cmp);

        for (int it = 0; it < m; it++){
            int i = nm[it];
            tch[i].PB(l[i]);

            MEM[l[i]][i] = sz(tct[l[i]]);
            tct[l[i]].PB(i);
            Ans[l[i]].PB(OO);
            int cur = l[i];
            bad = -(Y[i] - 1);

            while (1){
                fd = 0; pos = -1;
                search_right(1, 0, n - 1, cur + 1, r[i]);

                tch[i].PB(pos);

                MEM[pos][i] = sz(tct[pos]);
                tct[pos].PB(i);
                Ans[pos].PB(OO);
                cur = pos;

                if (pos == r[i])
                    break;
            }
        }

        for (int it = 0; it < sz(tct[s]); it++){
            Ans[s][it] = Y[tct[s][it]];
//            cerr << tct[s][it] << '\n';

            pq.insert({Ans[s][it], s, it});
        }

        while (sz(pq)){
            array<ll, 3> CR = (*pq.begin());
            pq.erase(pq.begin());

            int ps = CR[1], it = CR[2];
            int id = tct[ps][it];

            if (it > 0){
                ll nw = CR[0] + ll(Y[id]) - ll(Y[tct[ps][it - 1]]);

                if (Ans[ps][it - 1] > nw){
                    pq.erase({Ans[ps][it - 1], ps, it - 1});
                    Ans[ps][it - 1] = nw;
                    pq.insert({Ans[ps][it - 1], ps, it - 1});
                }
            }

            if (it + 1 < sz(tct[ps])){
                ll nw = CR[0] - ll(Y[id]) + ll(Y[tct[ps][it + 1]]);

                if (Ans[ps][it + 1] > nw){
                    pq.erase({Ans[ps][it + 1], ps, it + 1});
                    Ans[ps][it + 1] = nw;
                    pq.insert({Ans[ps][it + 1], ps, it + 1});
                }
            }

            int lc = -1;

            for (int ii = 0; ii < sz(tch[id]); ii++)
                if (tch[id][ii] == ps){
                    lc = ii;
                    break;
                }

            assert(lc != -1);

            if (lc > 0){
                int nps = tch[id][lc - 1];
                int nit = MEM[nps][id];

                ll nw = CR[0] + ll(x[ps]) - ll(x[nps]);

                if (Ans[nps][nit] > nw){
                    pq.erase({Ans[nps][nit], nps, nit});
                    Ans[nps][nit] = nw;
                    pq.insert({Ans[nps][nit], nps, nit});
                }
            }

            if (lc + 1 < sz(tch[id])){
                int nps = tch[id][lc + 1];
                int nit = MEM[nps][id];

                ll nw = CR[0] - ll(x[ps]) + ll(x[nps]);

                if (Ans[nps][nit] > nw){
                    pq.erase({Ans[nps][nit], nps, nit});
                    Ans[nps][nit] = nw;
                    pq.insert({Ans[nps][nit], nps, nit});
                }
            }
        }

        for (int it = 0; it < sz(tct[g]); it++)
            if (Ans[g][it] < OO)
                ans = min(ans, Ans[g][it] + ll(Y[tct[g][it]]));

        return (ans == OO ? -1 : ans);
    }

    bad = OO;

    for (int i = 0; i < m; i++)
        lines.PB({y[i], l[i], r[i]});

    sort(all(lines));

    for (int i = 0; i < m; ){
        int j = i;
        while (j < m && lines[j][0] == lines[i][0])
            j++;

        pii seg = MP(lines[i][1], lines[i][2]);
        int ht = lines[i][0];

        for (int I = i + 1; I < j; I++)
            if (seg.sd < lines[I][1]){
                events[seg.ft].PB(MP(-1, ht));
                events[seg.sd].PB(MP(+1, ht));

                seg = MP(lines[I][1], lines[I][2]);
            } else seg.sd = max(lines[I][2], seg.sd);

        events[seg.ft].PB(MP(-1, ht));
        events[seg.sd].PB(MP(+1, ht));

        i = j;
    }

    build(1, 0, sz(real_y) - 1);

    for (pii cr : events[0]){
        int ht = cr.sd;

        update(1, 0, sz(real_y) - 1, ht, real_y[ht]);
    }

    add(1, 0, sz(real_y) - 1, 0, sz(real_y) - 1, x[1] - x[0]);

    for (int loc = 1; loc < n - 1; loc++){
        sort(all(events[loc]));

        for (pii cr : events[loc]){
            int ht = cr.sd;

            if (cr.ft > 0){
                update(1, 0, sz(real_y) - 1, ht, OO);
            } else {
                push(1);
                if (st[1] == OO) return -1;

                ll best = OO;

                fd = 0; pos = -1; gt_vl = -1;

                search_left(1, 0, sz(real_y) - 1, 0, ht - 1);

                if (fd){
                    best = min(best, gt_vl + ll(real_y[ht]) - ll(real_y[pos]));
                }

                fd = 0; pos = -1; gt_vl = -1;

                search_right(1, 0, sz(real_y) - 1, ht + 1, sz(real_y) - 1);

                if (fd){
                    best = min(best, gt_vl - ll(real_y[ht]) + ll(real_y[pos]));
                }

                if (best == OO) return -1;

                update(1, 0, sz(real_y) - 1, ht, best);
            }
        }

        add(1, 0, sz(real_y) - 1, 0, sz(real_y) - 1, x[loc + 1] - x[loc]);
    }

    get_ans(1, 0, sz(real_y) - 1);

    return (ans == OO ? -1 : ans);
}

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