Submission #210458

#	Time	Username	Problem	Language	Result	Execution time	Memory
210458		mieszko11b	Sky Walking (IOI19_walk)	C++14	100 / 100	2968 ms	124076 KiB

walk

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

using namespace std;

using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;

#define X first
#define Y second

struct skywalk {
	int l, r, y;
	
	skywalk(int l, int r, int y) {
		this->l = l;
		this->r = r;
		this->y = y;
	}
};

int n;
vector<skywalk> S;
int maxv[20][100007];
map<ii, int> M;
int cnt;
vector<ii> G[600007];

void init_maxv(vector<int> &h) {
	for(int i = 0 ; i < n ; i++)
		maxv[0][i] = h[i];
	for(int k = 1 ; k < 19 ; k++)
		for(int i = 0 ; i < n ; i++)
			maxv[k][i] = max(maxv[k - 1][i], i + (1 << (k - 1)) < n ? maxv[k - 1][i + (1 << (k - 1))] : 0);	
}

int first_right(int x, int h) {
	int p = x - 1;
	for(int k = 18 ; k >= 0 ; k--)
		if(maxv[k][p + 1] < h)
			p += (1 << k);
	return p + 1;
}

int first_left(int x, int h) {
	int p = x + 1;
	for(int k = 18 ; k >= 0 ; k--)
		if(p - (1 << k) >= 0 && maxv[k][p - (1 << k)] < h)
			p -= (1 << k);
	return p - 1;
}

void reduce(int w) {
	vector<skywalk> SP;
	for(auto s : S) {
		if(s.l <= w && s.r >= w) {
			int a = first_left(w, s.y);
			int b = first_right(w, s.y);
			
			if(s.l < a)
				SP.emplace_back(s.l, a, s.y);
			if(a < b)
				SP.emplace_back(a, b, s.y);
			if(b < s.r)
				SP.emplace_back(b, s.r, s.y);
		} else {
			SP.push_back(s);
		}
	}
	swap(S, SP);
}

void build_graph(vector<int> &x, vector<int> &h) {
	multiset<int> active;
	vector<ii> E;
	map<int, int> lasti;
	set<ii> ready;
	
	for(auto s : S) {
		E.emplace_back(s.l, -s.y);
		E.emplace_back(s.r, s.y);
	}
	
	sort(E.begin(), E.end());
	
	int ind = 0;
	for(int i = 0 ; i < x.size() ; i++) {
		vector<int> interesting;
		
		int ind2 = ind;
		while(ind < E.size() && E[ind].X == i && E[ind].Y < 0) {
			active.insert(-E[ind].Y);
			ind++;
		}
		
		while(ind2 < E.size() && E[ind2].X == i) {
			int y = abs(E[ind2].Y);
			if(ready.count({i, y}) == 0) {
				interesting.push_back(y);
				ready.insert({i, y});
				if(M.count({i, y}) == 0)
					M[{i, y}] = ++cnt;
				auto it = active.lower_bound(y);
				int y2 = 0;
				if(it != active.begin())
					y2 = *(prev(it));
				if(M.count({i, y2}) == 0) {
					M[{i, y2}] = ++cnt;
					interesting.push_back(y2);
				}
				
				//~ cout << i << " " << y << " " << y2 << endl;
				
				int w = M[{i, y}];
				int u = M[{i, y2}];
				G[w].emplace_back(u, y - y2);
				G[u].emplace_back(w, y - y2);
			}

			ind2++;
		}
		
		for(int y : interesting) {
			//~ cout << "active: " << i << " " << y << " " << lasti[y] << endl;
			if(active.count(y) && lasti.count(y) > 0 && lasti[y] != -1 && lasti[y] < i) {
				int pi = lasti[y];
				
				if(M.count({i, y}) == 0)
					M[{i, y}] = ++cnt;
					
				if(M.count({pi, y}) == 0)
					M[{pi, y}] = ++cnt;
				
				int w = M[{i, y}];
				int u = M[{pi, y}];
				int d = x[i] - x[pi];
				G[w].emplace_back(u, d);
				G[u].emplace_back(w, d);
			}
			
			lasti[y] = i;
		}
		
		while(ind < E.size() && E[ind].X == i && E[ind].Y > 0) {
			active.erase(active.find(E[ind].Y));
			if(active.count(E[ind].Y) == 0)
				lasti[E[ind].Y] = -1;
			ind++;
		}
	}
}

void print_graph() {
	cout << cnt << " vertices:" << endl;
	for(auto p : M)
		cout << p.X.X << "," << p.X.Y << " -> " << p.Y << endl;
	cout << "edges:" << endl;
	for(int i = 1 ; i <= cnt ; i++) {
		cout << i << ": ";
		for(ii p : G[i])
			cout << "(" << p.X << ","<<p.Y <<") ";
		cout << endl;
	}
}

ll dist[600007];

ll find_dist(int s, int g) {
	int w = M[{s, 0}];
	
	if(!w || !M[{g, 0}])
		return -1;
	
	for(int i = 1 ; i <= cnt ; i++)
		dist[i] = 1e18;
	dist[w] = 0;
	
	//~ cout << w << endl;
	
	set<pll> S;
	S.insert({dist[w], w});
	
	while(!S.empty()) {
		auto p = *S.begin();
		S.erase(S.begin());
		
		for(auto p2 : G[p.Y]) {
			if(dist[p2.X] > dist[p.Y] + p2.Y) {
				S.erase((pll){dist[p2.X], p2.X});
				dist[p2.X] = dist[p.Y] + p2.Y;
				S.insert((pll){dist[p2.X], p2.X});
			}
		}
	}
	
	//~ for(int i = 1 ; i <= cnt ; i++)
		//~ cout << i << ": " << dist[i] << endl;
		
	
	return (dist[M[{g, 0}]] < ll(1e18)) ? dist[M[{g, 0}]] : -1;
}


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 = x.size();
	init_maxv(h);
		
	for(int i = 0 ; i < (int)l.size() ; i++)
		S.emplace_back(l[i], r[i], y[i]);
	
	reduce(s);
	reduce(g);
	
	//~ for(auto s : S)
		//~ cout << s.l << " " << s.r << " " << s.y << endl;
	//~ cout << "####################" << endl;
	build_graph(x, h);
	//~ print_graph();

	return find_dist(s, g);
}

Compilation message (stderr)

walk.cpp: In function 'void build_graph(std::vector<int>&, std::vector<int>&)':
walk.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < x.size() ; i++) {
                  ~~^~~~~~~~~~
walk.cpp:92:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind < E.size() && E[ind].X == i && E[ind].Y < 0) {
         ~~~~^~~~~~~~~~
walk.cpp:97:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2 < E.size() && E[ind2].X == i) {
         ~~~~~^~~~~~~~~~
walk.cpp:145:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind < E.size() && E[ind].X == i && E[ind].Y > 0) {
         ~~~~^~~~~~~~~~

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