Submission #251492

#	Time	Username	Problem	Language	Result	Execution time	Memory
251492		nvmdava	Sky Walking (IOI19_walk)	C++17	100 / 100	2063 ms	156668 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ll long long
#define ss second
const int N = 1000'005;

vector<int> br[N];
vector<pair<int, int> > adj[N];
int mx[N];
int n;

void build(vector<int>& h, int id, int l, int r){
	if(l == r){
		mx[id] = h[l];
		return;
	}
	int m = (l + r) >> 1;
	build(h, id << 1, l, m);
	build(h, id << 1 | 1, m + 1, r);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

int find_right(int id, int l, int r, int L, int R, int x){
	if(L > r || R < l) return -1;
	if(L <= l && r <= R){
		if(mx[id] < x) return -1;
		if(l == r) return r;
		int m = (l + r) >> 1;
		if(mx[id << 1 | 1] >= x) return find_right(id << 1 | 1, m + 1, r, L, R, x);
		return find_right(id << 1, l, m, L, R, x);
	}
	int m = (l + r) >> 1;
	int s = find_right(id << 1 | 1, m + 1, r, L, R, x);
	if(s != -1) return s;
	return find_right(id << 1, l, m, L, R, x);
}

int find_left(int id, int l, int r, int L, int R, int x){
	if(L > r || R < l) return -1;
	if(L <= l && r <= R){
		if(mx[id] < x) return -1;
		if(l == r) return r;
		int m = (l + r) >> 1;
		if(mx[id << 1] >= x) return find_left(id << 1, l, m, L, R, x);
		return find_left(id << 1 | 1, m + 1, r, L, R, x);
	}
	int m = (l + r) >> 1;
	int s = find_left(id << 1, l, m, L, R, x);
	if(s != -1) return s;
	return find_left(id << 1 | 1, m + 1, r, L, R, x);
}

vector<pair<int, int> > pos;
vector<pair<int, int> > sweep;

multiset<int> in;
map<pair<int, int>, int> id;
map<int, pair<int, int> > last;

void add(int v, int u, int d){
	adj[v].push_back({u, d});
	adj[u].push_back({v, d});
}

ll dis[N];
priority_queue<pair<ll, int> > pq;

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) {

	n = h.size();
	build(h, 1, 0, n - 1);

	for(int i = 0; i < l.size(); ++i){
		sweep.push_back({l[i], y[i]});
		sweep.push_back({l[i] + 1, y[i]});
		sweep.push_back({r[i] + 1, -y[i]});
		sweep.push_back({r[i] + 1, -y[i]});
		pos.push_back({l[i], -y[i]});
		pos.push_back({r[i], -y[i]});
		if(l[i] < s && s < r[i]){
			pos.push_back({find_left(1, 0, n - 1, s, r[i], y[i]), -y[i]});
			pos.push_back({find_right(1, 0, n - 1, l[i], s, y[i]), -y[i]});
		}
		if(l[i] < g && g < r[i]){
			pos.push_back({find_left(1, 0, n - 1, g, r[i], y[i]), -y[i]});
			pos.push_back({find_right(1, 0, n - 1, l[i], g, y[i]), -y[i]});
		}
	}

	sort(pos.begin(), pos.end());

	sort(sweep.begin(), sweep.end());

	int i = 0;
	in.insert(0);

	int tmp = 0;
	for(auto& w : pos){
		while(i < sweep.size() && sweep[i].ff <= w.ff){
			if(sweep[i].ss > 0) in.insert(-sweep[i].ss);
			else in.erase(in.find(sweep[i].ss));
			++i;
		}

		int x1 = w.ff, y1 = -w.ss, id1;
		int x2 = w.ff, y2 = -(*in.upper_bound(w.ss)), id2;

		if((id1 = id[{x1, y1}]) == 0)
			id1 = id[{x1, y1}] = ++tmp;
		if((id2 = id[{x2, y2}]) == 0)
			id2 = id[{x2, y2}] = ++tmp;
		add(id1, id2, y1 - y2);
		if(in.count(-y1) >= 2)
			add(id1, last[y1].ff, x[x1] - x[last[y1].ss]);
		if(in.count(-y2) >= 2)
			add(id2, last[y2].ff, x[x2] - x[last[y2].ss]);

		last[y2] = {id2, x2};
		last[y1] = {id1, x1};
	}

	int b = id[{g, 0}];
	for(int i = 0; i < N; ++i)
		dis[i] = 2'000'000'000'000'000'000;
	dis[b] = 0;
	pq.push({0, b});

	while(!pq.empty()){
		b = pq.top().ss;
		if(pq.top().ff != -dis[b]){
			pq.pop();
			continue;
		}
		pq.pop();

		for(auto& w : adj[b]){
			if(dis[w.ff] > dis[b] + w.ss){
				dis[w.ff] = dis[b] + w.ss;
				pq.push({-dis[w.ff], w.ff});
			}
		}
	}

	b = id[{s, 0}];

	return dis[b] == 0 || dis[b] == 2'000'000'000'000'000'000 ? -1 : dis[b];
}

Compilation message (stderr)

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:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < l.size(); ++i){
                 ~~^~~~~~~~~~
walk.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i < sweep.size() && sweep[i].ff <= w.ff){
         ~~^~~~~~~~~~~~~~

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