Submission #222623

#	Time	Username	Problem	Language	Result	Execution time	Memory
222623		VEGAnn	Sky Walking (IOI19_walk)	C++14	15 / 100	302 ms	17640 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;
vector<int> vc, real_y;
vector<array<int, 3> > lines;
vector<pii> events[N];
int n, m, pos;
bool fd;
ll st[4 * N], psh[4 * N], ans = OO, gt_vl;

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 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] < OO)
        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] < OO)
            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] < OO)
        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] < OO)
            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);
}

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);

    vc.clear();

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

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

//    for (int cr : real_y)
//        cerr << cr << " "; cerr << '\n';

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

    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;

                int lc = upper_bound(all(real_y), h[loc]) - real_y.begin() - 1;

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

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

                if (best == OO) return -1;

//                assert(best != OO);
//                if (best == OO){
//                    while (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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43