Submission #1207506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207506		HappyCapybara	Sky Walking (IOI19_walk)	C++17	33 / 100	226 ms	28616 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int G){
    int n = x.size();
	int m = l.size();
	vector<vector<pair<int,ll>>> g(m+2);
	vector<vector<int>> ev;
	for (int i=0; i<m; i++){
		ev.push_back({l[i], 1, i});
		ev.push_back({r[i], -1, i});
	}
	set<int> hs;
	map<int,int> htw;
	sort(ev.begin(), ev.end());
	int i = 0;
    //cout << "a" << endl;
	while (i < ev.size()){
        //cout << i << endl;
		int ct = ev[i][0];
		set<int> rm;
		while (i < ev.size() && ev[i][0] == ct && ev[i][1] == -1){
			hs.erase(y[ev[i][2]]);
			rm.insert(ev[i][2]);
            i++;
		}
		while (i < ev.size() && ev[i][0] == ct && ev[i][1] == 1){
			hs.insert(y[ev[i][2]]);
			htw[y[ev[i][2]]] = ev[i][2];
            i++;
		}
        //cout << "b" << endl;
		for (int w : rm){
			auto it = hs.upper_bound(y[w]);
			if (it != hs.end()) g[w].push_back({htw[*it], *it-y[w]});
			if (it != hs.begin()){
				it--;
				g[w].push_back({htw[*it], y[w]-*it});
				if (*it == y[w] && it != hs.begin()){
					it--;
					g[w].push_back({htw[*it], y[w]-*it});
				}
			}
		}
		if (ct == 0){
			for (int w : hs) g[m].push_back({htw[w], w});
		}
		if (ct == n-1){
			for (int w : rm) g[w].push_back({m+1, y[w]});
		}
	}
    /*for (int i=0; i<=m+1; i++){
        cout << i << endl;
        for (pair<int,int> next : g[i]) cout << next.first << " " << next.second << endl;
    }*/
	priority_queue<pair<ll,int>> pq;
	vector<bool> seen(m+2, false);
	pq.push({0, m});
    //cout << "c" << endl;
	while (!pq.empty()){
		ll d = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (seen[cur]) continue;
		seen[cur] = true;
		if (cur == m+1) return d+(ll)(x[n-1]-x[0]);
		for (pair<int,ll> next : g[cur]) pq.push({-(d+next.second), next.first});
	}
	return -1;
}

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