Submission #415485

#	Time	Username	Problem	Language	Result	Execution time	Memory
415485		wiwiho	Sky Walking (IOI19_walk)	C++14	33 / 100	319 ms	27816 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

const ll MAX = 1LL << 60;

struct SegmentTree{
    vector<ll> st;

    void resize(int n){
        st.resize(4 * n, MAX);
    }
        
    void modify(int pos, ll v, int L, int R, int id){
        if(L == R){
            st[id] = v;
            return;
        }
        int M = (L + R) / 2;
        if(pos <= M) modify(pos, v, L, M, 2 * id + 1);
        else modify(pos, v, M + 1, R, 2 * id + 2);
        st[id] = min(st[2 * id + 1], st[2 * id + 2]);
    }

    ll query(int l, int r, int L, int R, int id){
        if(l == L && r == R){
            return st[id];
        }
        int M = (L + R) / 2;
        if(r <= M) return query(l, r, L, M, 2 * id + 1);
        else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
        else return min(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
    }

};

int n, m;

vector<int> x, h, tl, tr, ty;
int sv, gv;
SegmentTree pre, suf;

vector<int> discr;
int sz;

int dcr(int v){
    return lower_bound(iter(discr), v) - discr.begin();
}

ll calc(int y){
    return min(discr[y] + pre.query(0, y, 0, sz - 1, 0), -discr[y] + suf.query(y, sz - 1, 0, sz - 1, 0));
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g){

    x = _x; h = _h; tl = _l; tr = _r; ty = _y; sv = _s; gv = _g;

    n = x.size();
    m = ty.size();
    assert(sv == 0 && gv == n - 1);

    discr = ty;
    discr.eb(0);
    lsort(discr);
    discr.resize(unique(iter(discr)) - discr.begin());
    sz = discr.size();

    pre.resize(sz);
    suf.resize(sz);

    vector<vector<int>> add(n), del(n);
    for(int i = 0; i < m; i++){
        add[tl[i]].eb(dcr(ty[i]));
        del[tr[i]].eb(dcr(ty[i]));
    }
    del[0].eb(0);

    pre.modify(0, 0, 0, sz - 1, 0);
    suf.modify(0, 0, 0, sz - 1, 0);
    vector<bool> use(sz);
    for(int i = 0; i < n - 1; i++){
        for(int j : add[i]){
            use[j] = true;
            ll v = calc(j);
            if(v == MAX) continue;
            //cerr << "test " << i << " " << discr[j] << " " << v << "\n";
            pre.modify(j, v - discr[j], 0, sz - 1, 0);
            suf.modify(j, v + discr[j], 0, sz - 1, 0);
        }
        for(int j : del[i]){
            if(use[j]) continue;
            pre.modify(j, MAX, 0, sz - 1, 0);
            suf.modify(j, MAX, 0, sz - 1, 0);
        }
        for(int j : add[i]) use[j] = false;
        //cerr << "test " << i << "  ";
        /*for(int j = 0; j < sz; j++){
            cerr << pre.query(j, j, 0, sz - 1, 0) + discr[j] << " ";
        }*/
        //cerr << "\n";
    }

    ll v = calc(0);
    if(v == MAX) return -1;
    return v + x[n - 1] - x[0];
}

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