Submission #293076

#	Time	Username	Problem	Language	Result	Execution time	Memory
293076		miss_robot	Sky Walking (IOI19_walk)	C++14	24 / 100	990 ms	133352 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"

#pragma GCC optimize("O3")
#define ll long long

using namespace std;

const int N = 100000;
const ll INF = numeric_limits<ll>::max()/4;
int n, m, s, e;
int x[N], h[N], l[N], r[N], y[N];

ll st1(){
	int c = n;
	vector< pair<int, int> > last(n, {-1, -1});
	vector< vector< pair<int, ll> > > g(c);
	vector< tuple<int, int, int> > sky(m);
	for(int i = 0; i < m; i++) sky[i] = {y[i], l[i], r[i]};
	sort(sky.rbegin(), sky.rend());
	set<int> building;
	vector< pair<int, int> > build(n);
	for(int i = 0; i < n; i++) build[i] = {h[i], i};
	sort(build.begin(), build.end());
	for(int i = 0; i < m; i++){
		while(!build.empty() && build.back().first >= get<0>(sky[i]))
			building.insert(build.back().second), build.pop_back();
		auto it = building.lower_bound(get<1>(sky[i]));
		int prev = -1, ind;
		while(it != building.end() && *it <= get<2>(sky[i])){
			int pos = *it, hi = get<0>(sky[i]);
			it++;
			g.resize(c+1);
			if(last[pos].first != -1){
				g[last[pos].first].push_back({c, last[pos].second-hi});
				g[c].push_back({last[pos].first, last[pos].second-hi});
			}
			last[pos] = {c, hi};
			if(prev != -1){
				g[ind].push_back({c, x[pos]-x[prev]});
				g[c].push_back({ind, x[pos]-x[prev]});
			}
			prev = pos, ind = c;
			c++;
		}
	}
	for(int i = 0; i < n; i++){
		if(last[i].first != -1){
			g[i].push_back({last[i].first, last[i].second});
			g[last[i].first].push_back({i, last[i].second});
		}
	}
	vector<ll> dis(c, INF);
	vector<int> vis(c);
	priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > q;
	dis[s] = 0;
	q.push({0, s});
	while(!q.empty()){
		int u = q.top().second, v;
		ll w;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		if(u == e) return dis[u];
		for(auto &t : g[u]){
			tie(v, w) = t;
			if(dis[v] > dis[u]+w){
				dis[v] = dis[u]+w;
				q.push({dis[v], v});
			}
		}
	}
	return -1;
}

ll st3(){
	ll sol = INF;
	set< pair<int, ll> > act;
	vector< vector<int> > start(n), end(n);
	for(int i = 0; i < m; i++){
		start[l[i]].push_back(y[i]);
		end[r[i]].push_back(y[i]);
	}
	for(int t : start[0]) act.insert({t, t});
	for(int i = 1; i < n; i++){
		if(act.empty()) return -1;
		set<int> ends, starts;
		for(int t : end[i]) ends.insert(t);
		for(int t : start[i]){
			if(ends.count(t)) continue;
			starts.insert(t);
			auto it = act.lower_bound({t, 0});
			ll cst = INF;
			if(it != act.end()) cst = min(cst, it->second + it->first - t);
			if(it != act.begin()) cst = min(cst, it->second + t - it->first);
			act.insert({t, cst});
		}
		if(i == n-1) break;
		for(int t : end[i]){
			if(starts.count(t)) continue;
			auto it = act.lower_bound({t, 0}), up = it, dwn = it;
			if(++up != act.end()){
				if(up->second > it->second + up->first - it->first){
					ll t1 = up->first, t2 = up->second + up->first - it->first;
					act.erase(up);
					act.insert({t1, t2});
				}
			}
			if(it != act.begin()){
				dwn--;
				if(dwn->second > it->second + it->first - dwn->first){
					ll t1 = dwn->first, t2 = it->second + it->first - dwn->first;
					act.erase(dwn);
					act.insert({t1, t2});
				}
			}
			act.erase(it);
		}
	}
	for(auto t : act) sol = min(sol, t.first + t.second);
	return sol + x[n-1] - x[0];
}

void wrt(vector<int>& X, vector<int>& H, vector<int>& L, vector<int>& R, vector<int>& Y, int S, int G){
	for(int i = 0; i < n; i++) x[i] = X[i], h[i] = H[i];
	for(int i = 0; i < m; i++) l[i] = L[i], r[i] = R[i], y[i] = Y[i];
	s = S, e = G;
}

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 = y.size();
	wrt(x, h, l, r, y, s, g);
	int s3 = 1;
	for(int i = 0; i < n-1; i++) if(h[i] != h[i+1]) s3 = 0;
	if(s3 && s == 0 && g == n-1) return st3();
	return st1();
}

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