Submission #1206742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206742		thelegendary08	Sky Walking (IOI19_walk)	C++17	24 / 100	776 ms	189576 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i =k; i<n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pii>
#define mii map<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define out(x) cout<<x<<endl;
#define out2(x,y) cout<<x<<' '<<y<<endl;
using namespace std;
using namespace __gnu_pbds;
const int mxn = (1e5 * 13);
vector<vpii>adj(mxn);
struct event{
	int x, d, type;
	
};
bool cmp(event a, event b){
	return b.x>a.x;
}
bool cmp2(pii a, pii b){
	if(a.first < b.first)return 1;
	else if(a.first > b.first)return 0;
	else return a.second < b.second;
}
typedef tree<pair<int,int>, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> osp;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) {
	//encode a position as h * n + i
	int n = x.size();
	int m = l.size();
	
	vvi pts(m);
	vector<pair<int,pair<pii,int>>>edges;
	f0r(i,m){
		edges.pb(mp(y[i], mp(mp(l[i], r[i]),i)));
	}
	sort(edges.rbegin(), edges.rend());
	os active;
	vector<pair<int, pii>> nodes;
	f0r(i,n){
		nodes.pb(mp(h[i], mp(x[i], i)));
	}
	sort(nodes.rbegin(), nodes.rend());
	int p1 = 0;
	int p2 = 0;
	vi nxt(n, -1);
	
	while(p1 < m){
		if(p2 == n){
			int dex = active.order_of_key(edges[p1].second.first.first);
			// auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first);
			int cur = *active.find_by_order(dex);
			int d = edges[p1].second.second;
			while(cur != -1 && cur <= edges[p1].second.first.second){
				pts[d].pb(cur);
				cur = nxt[cur];
			}
			p1++;
		}
		else{
			if(edges[p1].first > nodes[p2].first){
				//compute edge
				int dex = active.order_of_key(edges[p1].second.first.first);
				// auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first);
				int cur = *active.find_by_order(dex);
				int d = edges[p1].second.second;
				while(cur != -1 && cur <= edges[p1].second.first.second){
					pts[d].pb(cur);
					cur = nxt[cur];
				}
				p1++;
			}
			else{
				int dex = active.order_of_key(nodes[p2].second.second);
				// auto it = lower_bound(active.begin(), active.end(), nodes[p2].second.second);
				if(dex != active.size())nxt[nodes[p2].second.second] = *active.find_by_order(dex);
				if(dex != 0){
					dex--;
					nxt[(*active.find_by_order(dex))] = nodes[p2].second.second;
					// nxt[*it] = nodes[p2].second.second;
				}
				active.insert(nodes[p2].second.second);
				p2++;
			}
		}
	}
	f0r(i,m){
		sort(pts[i].begin(), pts[i].end());
	}
	
	
	
	
	vector<vpii> ints(n);
	int cnt = n;
	f0r(i,m){
		for(int k = 0; k<pts[i].size(); k++){
			int j = pts[i][k];
			ints[j].pb(mp(y[i], cnt));
			cnt++;
			if(k > 0){
				int j = pts[i][k-1];
				int j2 = pts[i][k];
				adj[cnt-1].pb(mp(cnt-2, x[j2] - x[j]));
				adj[cnt-2].pb(mp(cnt-1, x[j2] - x[j]));
			}
		}
	}

	f0r(i,n){
		ints[i].pb(mp(0, i));
	}
	f0r(i,n){
		sort(ints[i].begin(), ints[i].end());
	}
	f0r(i,n){
		f0r(j, ints[i].size() - 1){
			int h1 = ints[i][j].first;
			int h2 = ints[i][j+1].first;
			adj[ints[i][j].second].pb(mp(ints[i][j+1].second, h2-h1));
			adj[ints[i][j+1].second].pb(mp(ints[i][j].second, h2-h1));
		}
	}
	
	vi dist(mxn, 4e18);
	dist[s] = 0;
	priority_queue<pii>q;
	q.push(mp(0,s));
	while(!q.empty()){
		int node = q.top().second;
		q.pop();
		for(auto u : adj[node]){
			int b = u.first;
			int w = u.second;
			if(dist[b] > dist[node] + w){
				dist[b] = dist[node] + w;
				q.push(mp(-dist[b], b));
			}
		}
	}
	
	
	/*
	out(dist[n + 1]);
	out(dist[6 * n + 1]);
	out(dist[6 * n + 2]);
	out(dist[7*n+2]);
	out(dist[7*n+6]);
	out(dist[5*n+6]);
	out(dist[5*n+5]);
	*/
	/*
	vector<event>events;
	f0r(i, m){
		events.pb({l[i], i, 0});
		events.pb({r[i], i, 1});
	}
	sort(events.begin(), events.end(), cmp);
	
	osp s;
	f0r(i, events.size()){
		if(events[i].type == 0){
			s.insert(mp(y[events[i].d], events[i].d));
		}
		else{
			int dex = s.order_of_key(mp((int)y[events[i].d], -1LL));
			// auto it = lower_bound(s.begin(), s.end(), mp((int)y[events[i].d], -1LL));
			if(events[i].d == 2){
				// dout(y[events[i].d]);
				// dout(s.size());
			}
			if(dex != s.size())adj[events[i].d].pb((*s.find_by_order(dex)).second);
			if(dex != 0){
				dex--;
				adj[events[i].d].pb((*s.find_by_order(dex)).second);
			}
		}
	}
	vi dist(mxn, 4e18);
	dist[mxn-2] = 0;
	priority_queue<pii>q;
	f0r(i, m){
		if(l[i] == 0){
			adj[mxn-2].pb(i);
		}
		if(r[i] == n-1){
			adj[i].pb(mxn-1);
		}
	}
	q.push(mp(0,mxn-2));
	while(!q.empty()){
		int node = q.top().second;
		// dout(node);
		q.pop();
		for(auto u : adj[node]){
			int b = u;
			int w;
			if(node == mxn-2){
				w = y[b];
			}
			else if(b == mxn - 1){
				w = y[node];
			}
			else{
				w = abs(y[node] - y[b]);
			}
			if(dist[b] > dist[node] + w){
				dist[b] = dist[node] + w;
				q.push(mp(-dist[b], b));
			}
		}
	}
	*/
	if(dist[g] == 4e18)return -1;
	else return dist[g];
	
	
	return 1;
}

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