Submission #1071462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071462		becaido	Sky Walking (IOI19_walk)	C++17	57 / 100	1321 ms	1048576 KiB

walk

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "walk.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1e5 + 5;

int n, m, s, e, sz;
vector<int> y[SIZE];
int x[SIZE], h[SIZE];
vector<pair<int, int>> P, Q;
tuple<int, int, int> a[SIZE];
vector<tuple<int, int, int>> ed;

int get_id(int i, int y) {
    return lower_bound(P.begin(), P.end(), make_pair(i, y)) - P.begin() + 1;
}

set<pair<int, int>> seg;
void split(int p) {
    auto it = prev(seg.lower_bound({p + 1, 0}));
    if (it->F != p) seg.emplace(p, it->S);
}
void upd(int l, int r, int y) {
    split(l), split(r + 1);
    for (auto it = seg.lower_bound({l, 0}); it->F <= r; it = seg.erase(it));
    seg.emplace(l, y);
}
int get_h(int p) {
    auto it = prev(seg.lower_bound({p + 1, 0}));
    return it->S;
}

ll same() {
    seg.emplace(1, 0);
    seg.emplace(n + 1, 0);
    sort(a + 1, a + m + 1);
    FOR (i, 1, n) y[i].pb(0);
    FOR (i, 1, m) {
        auto [h, l, r] = a[i];
        y[l].pb(h), y[r].pb(h);
        y[l].pb(get_h(l));
        y[r].pb(get_h(r));
        upd(l, r, h);
    }
    seg.clear();
    seg.emplace(1, inf);
    seg.emplace(n + 1, inf);
    for (int i = m; i >= 1; i--) {
        auto [h, l, r] = a[i];
        int hl = get_h(l), hr = get_h(r);
        if (hl != inf) y[l].pb(hl);
        if (hr != inf) y[r].pb(hr);
        upd(l, r, h);
    }

    FOR (i, 1, n) {
        sort(y[i].begin(), y[i].end());
        y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
        for (int iy : y[i]) P.pb(i, iy), Q.pb(iy, i);
        sz += y[i].size();
    }
    sort(Q.begin(), Q.end());

    vector<ll> dis(sz + 1, INF);
    vector<vector<pair<int, int>>> adj(sz + 1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
        int u = get_id(i, y[i][j]), v = get_id(i, y[i][j + 1]);
        adj[u].pb(v, y[i][j + 1] - y[i][j]);
        adj[v].pb(u, y[i][j + 1] - y[i][j]);
    }
    FOR (i, 1, m) {
        auto [h, l, r] = a[i];
        int j = lower_bound(Q.begin(), Q.end(), make_pair(h, l)) - Q.begin();
        while (Q[j].S < r) {
            int u = get_id(Q[j].S, h), v = get_id(Q[j + 1].S, h), d = x[Q[j + 1].S] - x[Q[j].S];
            adj[u].pb(v, d);
            adj[v].pb(u, d);
            j++;
        }
    }
    s = get_id(s, 0), e = get_id(e, 0);
    pq.emplace(dis[s] = 0, s);
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
            pq.emplace(dis[np] = d + w, np);
        }
    }
    return dis[e] == INF ? -1 : dis[e];
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g) {
    n = _x.size(), m = _l.size();
    s = _s + 1, e = _g + 1;
    FOR (i, 1, n) {
        x[i] = _x[i - 1];
        h[i] = _h[i - 1];
    }
    FOR (i, 1, m) {
        _l[i - 1]++, _r[i - 1]++;
        a[i] = {_y[i - 1], _l[i - 1], _r[i - 1]};
    }

    if (s == 1 && e == n) return same();

    set<int> st;
    FOR (i, 1, n) st.insert(i), y[i].pb(0);
    vector<tuple<int, int, int>> all;
    FOR (i, 1, m) all.pb(a[i]);
    FOR (i, 1, n) all.pb(h[i], x[i], -i);
    sort(all.begin(), all.end(), [&](auto x, auto y) {
        return get<0>(x) != get<0>(y) ? get<0>(x) < get<0>(y) : get<2>(x) > get<2>(y);
    });
    for (auto [a, b, c] : all) {
        if (c < 0) {
            st.erase(-c);
            continue;
        }
        int last = 0;
        for (auto it = st.lower_bound(b); it != st.end() && *it <= c; it++) {
            y[*it].pb(a);
            if (last != 0) ed.pb(last, *it, a);
            last = *it;
        }
    }
    FOR (i, 1, n) {
        sort(y[i].begin(), y[i].end());
        y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
        for (int iy : y[i]) P.pb(i, iy);
        sz += y[i].size();
    }
    sort(ed.begin(), ed.end());
    ed.erase(unique(ed.begin(), ed.end()), ed.end());

    vector<ll> dis(sz + 1, INF);
    vector<vector<pair<int, int>>> adj(sz + 1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (auto [i, j, y] : ed) {
        int u = get_id(i, y), v = get_id(j, y);
        adj[u].pb(v, x[j] - x[i]);
        adj[v].pb(u, x[j] - x[i]);
    }
    FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
        int u = get_id(i, y[i][j]), v = get_id(i, y[i][j + 1]);
        adj[u].pb(v, y[i][j + 1] - y[i][j]);
        adj[v].pb(u, y[i][j + 1] - y[i][j]);
    }
    s = get_id(s, 0), e = get_id(e, 0);
    pq.emplace(dis[s] = 0, s);
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
            pq.emplace(dis[np] = d + w, np);
        }
    }
    return dis[e] == INF ? -1 : dis[e];
}

/*
in1
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
out1
27

in2
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
out2
21
*/

Compilation message (stderr)

walk.cpp: In function 'long long int same()':
walk.cpp:92:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
      |                                   ~~~~~~^~~~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:171:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
      |                                   ~~~~~~^~~~~~~~~~~~~

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