Submission #825824

#	Time	Username	Problem	Language	Result	Execution time	Memory
825824		tomruk	Sky Walking (IOI19_walk)	C++17	57 / 100	4089 ms	480928 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,long long> d[N];
vector<int> vv[N];
vector<int> add[N];
vector<int> del[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = p.size();
	int m = l.size();
	if(s == 0 && g == n-1){
		vector<pair<int,int>> v;
		for(int i = 0;i<n;i++){
			v.push_back({h[i],i});
			adj[i][0].push_back(i);
		}
		for(int i = 0;i<m;i++){
			vv[r[i]].push_back(i);
			v.push_back({y[i],~i});
			add[r[i]].push_back(i);
			del[l[i]].push_back(i);
		}
		set<pair<int,int>> act;
		for(int i = n-1;i>=0;i--){
			for(auto u:add[i]){
				act.insert({y[u],u});
			}
			// cout << "asdasd" << endl;
			// cout << i << endl;
			// for(auto u:act){
			// 	cout << u.first << " " << u.second << endl;
			// }
			for(auto u:vv[i]){
				// cout << u << endl;
				auto it = act.lower_bound({y[u],u});
				if(next(it) != act.end()){
					adj[i][next(it)->first].push_back(r[next(it)->second]);
					adj[r[next(it)->second]][next(it)->first].push_back(i);
				}
				if(it != act.begin()){
					adj[i][prev(it)->first].push_back(r[prev(it)->second]);
					adj[r[prev(it)->second]][prev(it)->first].push_back(i);
				}
			}
			for(auto u:del[i]){
				act.erase({y[u],u});
			}
		}
		sort(v.rbegin(),v.rend());
		set<int> active;
		for(auto u:v){
			if(u.second < 0){
				u.second = ~u.second;
				auto it = active.lower_bound(max(s,l[u.second]));
				auto it2 = active.lower_bound(min(g,r[u.second]));
				adj[*it][y[u.second]].push_back(*it2);
				adj[*it2][y[u.second]].push_back(*it);
				// while(1){
				// 	auto it2 = it;
				// 	it2++;
				// 	if(it2 == active.end() || *it2 > r[u.second])
				// 		break;
				// 	adj[*it][y[u.second]].push_back(*it2);
				// 	adj[*it2][y[u.second]].push_back(*it);
				// 	it = it2;
				// }
			}
			else{
				active.insert(u.second);
			}
		}
		priority_queue<pair<long long,pair<int,int>>> q;
		d[s][0] = 0;
		q.push({-d[s][0],{s,0}});
		while(q.size()){
			auto tp = q.top();
			q.pop();
			tp.first *= -1;
			int x = tp.second.first;
			int y = tp.second.second;
			if(tp.first != d[x][y])
				continue;
			// cout << x << ' ' << y << endl;
			// cout << tp.first << endl;
			for(auto u:adj[x][y]){
				long long nw = abs(p[x] - p[u]) + tp.first;
				if(d[u].count(y) == 0 || d[u][y] > nw){
					d[u][y] = nw;
					q.push({-d[u][y],{u,y}});
				}
			}
			auto it = adj[x].find(y);
			if(next(it) != adj[x].end()){
				long long nw = abs(y - next(it)->first) + tp.first;
				if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
					d[x][next(it)->first] = nw;
					q.push({-d[x][next(it)->first],{x,next(it)->first}});
				}
			}
			if(it != adj[x].begin()){
				long long nw = abs(y - prev(it)->first) + tp.first;
				if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
					d[x][prev(it)->first] = nw;
					q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
				}
			}
		}
		return (d[g].count(0)?d[g][0]:-1);
	}
		vector<pair<int,int>> v;
	for(int i = 0;i<n;i++){
		v.push_back({h[i],i});
		adj[i][0].push_back(i);
	}
	for(int i = 0;i<m;i++){
		v.push_back({y[i],~i});
	}
	sort(v.rbegin(),v.rend());
	set<int> active;
	for(auto u:v){
		if(u.second < 0){
			u.second = ~u.second;
			auto it = active.lower_bound(l[u.second]);
			while(1){
				auto it2 = it;
				it2++;
				if(it2 == active.end() || *it2 > r[u.second])
					break;
				adj[*it][y[u.second]].push_back(*it2);
				adj[*it2][y[u.second]].push_back(*it);
				it = it2;
			}
		}
		else{
			active.insert(u.second);
		}
	}
	priority_queue<pair<long long,pair<int,int>>> q;
	d[s][0] = 0;
	q.push({-d[s][0],{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		int x = tp.second.first;
		int y = tp.second.second;
		if(tp.first != d[x][y])
			continue;
		// cout << x << ' ' << y << endl;
		// cout << tp.first << endl;
		for(auto u:adj[x][y]){
			long long nw = abs(p[x] - p[u]) + tp.first;
			if(d[u].count(y) == 0 || d[u][y] > nw){
				d[u][y] = nw;
				q.push({-d[u][y],{u,y}});
			}
		}
		auto it = adj[x].find(y);
		if(next(it) != adj[x].end()){
			long long nw = abs(y - next(it)->first) + tp.first;
			if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
				d[x][next(it)->first] = nw;
				q.push({-d[x][next(it)->first],{x,next(it)->first}});
			}
		}
		if(it != adj[x].begin()){
			long long nw = abs(y - prev(it)->first) + tp.first;
			if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
				d[x][prev(it)->first] = nw;
				q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
			}
		}
	}
	return (d[g].count(0)?d[g][0]:-1);
}

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