Submission #1048882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048882		mychecksedad	Sky Walking (IOI19_walk)	C++17	0 / 100	45 ms	192252 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 2e6+100, K = 20, M=2E5;

int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<pair<int,int>> T[N];
vector<int> F[N];
vector<pair<int, ll>> g[N];
int rmq[M][K];
int get(int l, int r){
	int k = log2(r-l+1);
	return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
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 gg) {
	n = x.size();
	m = l.size();
	for(int i = 0; i < m; ++i){
		int u = l[i], v = r[i], L = y[i];
		// F[u].pb(L);
		// F[v].pb(L);
		if(u>v) swap(u,v);
		G[u].pb({v, L});
		T[v].pb({u, L});
	}


	if(s == 0 && gg == n-1){
		set<pair<ll, ll>> S;
		// S.insert({0, 0});
		for(auto u: G[0]){
			S.insert({u.ss, u.ss});
		}

		for(int i = 1; i < n; ++i){	
			for(auto U : T[i - 1]){
				int u = U.ss;
				auto it = S.lower_bound(pair<ll,ll>{u, 0ll});
				if(it != S.end() && (*it).first == u){
					S.erase(it);
				}
			}
			if(S.empty()){
				return -1;
			}
			vector<pair<ll, ll>> ins;
			for(auto U: G[i]){
				ll u = U.ss;
				// cout << i << ' ' << u << '\n';
				auto it = S.lower_bound(pair<ll,ll>{u, 0ll});
				ll val = 1e15;
				if(it != S.end() && (*it).first <= h[i]){
					val = min(val, abs((*it).first - u) + (*it).second);
				}
				if(it != S.begin()){ it = prev(it);
					val = min(val, abs((*it).first - u) + (*it).second);
				}
				ins.pb({u, val});
			}
			
			for(auto p: ins) S.insert(p);
		}
		ll uwu = 1e15;
		for(auto x: S){
			uwu=min(uwu, x.ss + x.ff);
			// cout << x.ss << ' ' << x.ff << '\n';
		}
		if(uwu > 1e15){
			return -1;
		}
		return x[n-1]-x[0] + uwu;
	}


	

	for(int i = 1; i <= n; ++i) rmq[i][0] = h[i - 1];
	for(int j = 1; j < K ;++j){
		for(int i = 1; i + (1<<j) <= n+1; ++i){
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j-1]);
		}
	}

	int co = 0;
	for(int i = 0; i < n; ++i){
		for(auto U: G[i]){
			int u = U.ff; ll w = U.ss;
			if(u > i){
				if(node[{i,w}] == 0)
				node[{i, w}] = co++;
				int last = i;
				while(last < u){
					int l = last + 2, r = n, p = n + 1;
					while(l <= r){
						int mid = l+r>>1;
						if(get(last + 2, mid) >= w){
							p = mid;
							r = mid - 1;
						}else{
							l = mid + 1;
						}
					}
					--p;
					if(h[p] >= w){
						if(node[{p,w}]==0)
						node[{p, w}] = co++;
						// cout << x[p] << ' ' << x[last] << '\n';
						g[node[{last, w}]].pb({node[{p,w}], abs(x[p] - x[last])});
						g[node[{p,w}]].pb({node[{last, w}], abs(x[p] - x[last])});
						F[p].pb(w);
					}
					last = p;
				}
				
			}
		}
	}
	for(int i = 0; i < n; ++i){
		F[i].pb(0);
		// F[i].pb(h[i]);
		sort(all(F[i]));
		F[i].erase(unique(all(F[i])), F[i].end());
		vector<int> X;
		if(node[{i,0}]==0) node[{i, 0}] = co++;
		// if(node[{i,h[i]}]==0) node[{i, 0}] = co++;
		for(int p: F[i]){
			// cout << i << ' ' <<p << '\n';
			// node[{i, p}] = co++;
			X.pb(node[{i, p}]);
		}
		for(int j = 0; j + 1 < F[i].size(); ++j){
			// cout << F[i][j] << ' ';
			g[X[j]].pb({X[j+1], F[i][j + 1] - F[i][j]});
			g[X[j + 1]].pb({X[j], F[i][j + 1] - F[i][j]});
		}
		// cout << '\n';
	}
	// cout << "\n";
	// for(int i = 0; i < n; ++i){
	// 	for(auto U: G[i]){
	// 		int u = U.ff; ll w = U.ss;
	// 		if(u > i){
	// 			int last = i;
	// 			int j = u;
	// 			g[node[{last, w}]].pb({node[{j, w}], abs(x[j]-x[last])});
	// 			g[node[{j, w}]].pb({node[{last, w}], abs(x[j]-x[last])});
	// 			last = j;
	// 		}
	// 	}
	// }
	vector<ll> dist(co, 1e15*1ll);
	vector<bool> vis(co);
	priority_queue<pair<ll, int>> Q;
	Q.push({0, node[{s, 0}]});
	dist[node[{s, 0}]] = 0;
	while(!Q.empty()){
		int v = Q.top().ss; Q.pop();
		if(vis[v]) continue;
		// cout  << v << ' ' << dist[v] << '\n';
		vis[v] = 1;
		for(auto U: g[v]){
			int u = U.ff;
			ll w= U.ss;
			if(dist[u] > dist[v] + w){
				dist[u] = dist[v] + w;;
				Q.push({-dist[u], u});
			}
		}
	}
	ll D = dist[node[{gg, 0}]];
	if(D == 1e15*1ll) return -1;
	// cout << node[{gg,0}] << ' ';
	return D;
}

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:103:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |       int mid = l+r>>1;
      |                 ~^~
walk.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int j = 0; j + 1 < F[i].size(); ++j){
      |                  ~~~~~~^~~~~~~~~~~~~

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