Submission #222726

#	Time	Username	Problem	Language	Result	Execution time	Memory
222726		VEGAnn	Sky Walking (IOI19_walk)	C++14	15 / 100	318 ms	21020 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