Submission #1187165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187165		crafticat	Sky Walking (IOI19_walk)	C++20	43 / 100	601 ms	52092 KiB

walk

#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stdexcept>
#include <string>
#include <tuple>
#include <queue>

#define DEBUG 0

using namespace std;

#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for (ll i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using ll = long long;
using vi = V<ll>;

using pi = pair<ll, ll>;
V<V<V<pair<ll,ll> > > > G;
ll GID = 0;

void addEdge(ll a, ll b, ll c) {
    G[GID][a].push_back(make_pair(b, c));
    G[GID][b].push_back(make_pair(a, c));

}

V<ll> diks(ll root, ll calcId) {
    vi vis(G[GID].size());
    V<ll> dp(G[GID].size(), -1);

    priority_queue<pair<ll, ll>, V<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    pq.push(make_pair(0, root));

    while (!pq.empty()) {
        const auto [d, n] = pq.top(); pq.pop();
        if (vis[n]) continue;
        vis[n] = 1;
        dp[n] = d;

        for (const auto [y, c] : G[calcId][n]) {
            if (vis[y]) continue;
            pq.push(make_pair(d + c, y));
        }
    }

    return dp;
}

void addAll(set<pi> &heights, set<pair<ll, pi> > &wait) {
    wait.clear();
    ll lastH = -1, lastId = -1;
    for (const auto [h, id] : heights) {
        if (lastH != -1) {
            wait.insert(make_pair(h, make_pair(max(lastId, id), min(lastId, id))));
        }

        lastH = h;
        lastId = id;
    }
}

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) {
    G.resize(3,V<V<pair<ll,ll> > >(l.size() + 2));

    V<pair<pi, ll> > updates; // Inset (l, index), delete (x, index), build (x, h) (x, type) -> data
    // inset, build, erase

    F0R(i, x.size()) {
        updates.push_back(make_pair(make_pair(x[i], 2),i));
    }
    F0R(i, l.size()) {
        updates.push_back(make_pair(make_pair(x[l[i]], 1), i));
        updates.push_back(make_pair(make_pair(x[r[i]], 3), i));
    }
    sort(updates.begin(), updates.end());
    set<pi> heights;
    set<pi> hb, ha;
    set<pi> tempH;
    set<pair<ll, pi> > wait;
    vi to(l.size() + 2, -1), from(l.size() + 2);
    if (x[s] > x[g]) swap(s, g);

    for (const auto [v, data] : updates) {
        const auto [x, type] = v;

        if (type == 1) {
            auto it = heights.lower_bound(make_pair(y[data], data));
            ll top = -1, bot = -1;
            if (it != heights.end()) {
                wait.insert(make_pair(it->first, make_pair(max(data, it->second), min(data, it->second))));
                top = it->second;
            }
            if (it != heights.begin()) {
                it--;
                wait.insert(make_pair(it->first, make_pair(max(data, it->second), min(data, it->second))));
                bot = it->second;
            }
            if (bot != -1 && top != -1) {
                wait.erase(make_pair(y[top], make_pair(max(top, bot), min(top, bot))));
            }

            heights.insert(make_pair(y[data], data));
            tempH.insert(make_pair(y[data], data));
        }
        if (type == 3) {
            auto it = heights.lower_bound(make_pair(y[data], data));
            it++;
            ll top = -1, bot = -1;
            if (it != heights.end()) {
                wait.erase(make_pair(it->first, make_pair(max(data, it->second), min(data, it->second))));
                top = it->second;
            }
            it--;
            if (it != heights.begin()) {
                it--;
                wait.erase(make_pair(it->first, make_pair(max(data, it->second), min(data, it->second))));
                bot = it->second;
            }
            if (bot != -1 && top != -1) {
                wait.insert(make_pair(y[top], make_pair(max(top, bot), min(top, bot))));
            }

            heights.erase(make_pair(y[data], data));
            if (tempH.count(make_pair(y[data], data))) tempH.erase(make_pair(y[data], data));
        }

        if (type == 2) {
            if (data == g) {
                GID++;
                addAll(heights, wait);
            }
            if (data == s || data == g) {
                ll node = (data == s ? 0 : 1) + l.size();
                for (const auto [hi, id] : heights) {
                    if (hi > h[data]) continue; // out of bounce
                    addEdge(node, id, hi);
                }
            }
            if (data == s)
                hb = heights;
            if (data == g)
                ha = heights;

            while (!tempH.empty() && GID == 2) {
                auto it = tempH.begin();
                if (it->first <= h[data]) {
                    to[it->second] = x;
                    tempH.erase(it);
                } else break;
            }

            while (!wait.empty()) {
                auto it = wait.begin();
                if (it->first <= h[data]) {
                    addEdge(it->second.first, it->second.second, abs(y[it->second.first] - y[it->second.second]));
                    wait.erase(it);
                } else break;
            }
            if (data == s) {GID++;
                addAll(heights, wait);

            }
        }
    }
    reverse(updates.begin(), updates.end());
    tempH.clear();
    GID = 0;
    for (const auto [v, data] : updates) {
        const auto [x, type] = v;

        if (type == 3) {
            tempH.insert(make_pair(y[data], data));
        }
        if (type == 1) {
            if (tempH.count(make_pair(y[data], data))) tempH.erase(make_pair(y[data], data));
        }

        if (type == 2) {
            if (data == s)
                 {
                    GID++;
                }

            while (!tempH.empty() && GID == 2) {
                auto it = tempH.begin();
                if (it->first <= h[data]) {
                    from[it->second] = x;
                    tempH.erase(it);
                } else break;
            }
            if (data == g) GID++;
        }
    }


    V<ll> d1 = diks(l.size(), 0);
    V<ll> d3 = diks(l.size() + 1, 2);
    GID = 1;
    for (const auto [h, i] : hb) {
        if (d1[i] == -1) continue;
        addEdge(l.size(), i, d1[i] + (x[s] - from[i]) * 2);
    }
    for (const auto [h, i] : ha) {
        if (d3[i] == -1) continue;
        if (to[i] == -1) exit(5);
        addEdge(l.size() + 1, i, d3[i] + (to[i] - x[g]) * 2);
    }
    V<ll> d2 = diks(l.size(), 1);
    ll v = d2[l.size() + 1];

    if (v == -1) return -1;
    return v + x[g] - x[s];
}

#if DEBUG

using namespace std;

int main() {
	ll n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<ll> x(n), h(n);
	for (ll i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<ll> l(m), r(m), y(m);
	for (ll i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	ll s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	prllf("%lld\n", result);
	fclose(stdout);
	return 0;
}
#endif

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