Submission #592378

#	Time	Username	Problem	Language	Result	Execution time	Memory
592378		8e7	Sky Walking (IOI19_walk)	C++17	100 / 100	1683 ms	243524 KiB

walk

//Challenge: Accepted
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r)cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxv 3000005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<60;
vector<pii> adj[maxv];
ll dis[maxv];
int prv[maxn], px[maxn];
vector<int> lft[maxn], rht[maxn];
bool on[maxn];

struct segtree{
	int seg[4 * maxn];
	void init(int cur, int l, int r, vector<int> &h) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = h[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, h), init(cur*2+1, m, r, h);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	int search(int cur, int l, int r, int ql, int qr, int x, bool type) {
		if (r <= l || ql >= r || qr <= l || seg[cur] < x) return -1;
		if (r - l == 1) return l;
		int m = (l + r) / 2;
		if (type == 0) {
			int vl = search(cur*2, l, m, ql, qr, x, type);
			if (vl != -1) return vl;
			else return search(cur*2+1, m, r, ql, qr, x, type);
		} else {
			int vr = search(cur*2+1, m, r, ql, qr, x, type);
			if (vr != -1) return vr;
			else return search(cur*2, l, m, ql, qr, x, type);
		}
	}	
} tr;
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int st, int ed) {
	int n = X.size(), m = L.size();
	tr.init(1, 0, n, H);	

	set<pii> se;	
	for (int i = 0;i < m;i++) {
		int l = L[i], r = R[i], y = Y[i];
		lft[l].push_back(i), rht[r].push_back(i);
		if (l <= st && r >= st) {
			int vl = tr.search(1, 0, n, l, st+1, y, 1), vr = tr.search(1, 0, n, st+1, r+1, y, 0);
			if (vl != -1) lft[vl].push_back(i);	
			if (vr != -1) lft[vr].push_back(i);
		}
		if (l <= ed && r >= ed) {
			int vl = tr.search(1, 0, n, l, ed+1, y, 1), vr = tr.search(1, 0, n, ed+1, r+1, y, 0);
			if (vl != -1) lft[vl].push_back(i);	
			if (vr != -1) lft[vr].push_back(i);
		}
	}
	auto addedge = [&] (int u, int v, int w){
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		//debug(u, v, w);
	};
	debug();
	int term = maxv - 1;
	{
		int cur = 1;
		for (int i = 0;i < n;i++) {
			vector<int> ev = lft[i];
			ev.insert(ev.end(), rht[i].begin(), rht[i].end());
			sort(ev.begin(), ev.end());
			ev.resize(int(unique(ev.begin(), ev.end()) - ev.begin()));
			//pary(ev.begin(), ev.end());
			for (int id:ev) {
				int y = Y[id], node = cur++;
				//debug("node", node, X[i], Y[id]);
				if (i == st && y <= H[i]) addedge(node, 0, y);
				if (i == ed && y <= H[i]) addedge(node, term, y);
				
				{
					auto it = se.upper_bound(make_pair(y, id));
					if (it != se.end() && it->ff <= H[i]) {
						addedge(cur, prv[it->ss], X[i] - px[it->ss]);
						prv[it->ss] = cur;
						px[it->ss] = X[i];
						//debug("node", cur, X[i], it->ff);
						addedge(node, cur++, abs(y - it->ff));	
					}
				}
				{
					auto it = se.lower_bound(make_pair(y, id));
					if (it != se.begin()) {
						it = prev(it);
						addedge(cur, prv[it->ss], X[i] - px[it->ss]);
						prv[it->ss] = cur;
						px[it->ss] = X[i];
						//debug("node", cur, X[i], it->ff);
						addedge(node, cur++, abs(y - it->ff));	
					}
				}

				if (on[id]) {
					addedge(node, prv[id], X[i] - px[id]);
				} else {
					se.insert(make_pair(y, id));
					on[id] = 1;
				}
				prv[id] = node;
				px[id] = X[i];
				 
			}
			for (int id:rht[i]) {
				se.erase(se.find(make_pair(Y[id], id)));
			}
		}
	}
	for (int i = 0;i < maxv;i++) dis[i] = inf;	
	dis[0] = 0;	
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.push({0, 0});
	while (pq.size()) {
		auto [d, cur] = pq.top();
		pq.pop();
		if (d != dis[cur]) continue;
		for (auto [v, w]:adj[cur]) {
			if (d + w < dis[v]) {
				dis[v] = d + w;
				pq.push({dis[v], v});
			}
		}
	}
	if (dis[term] == inf) return -1;
	return dis[term];
}

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:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
walk.cpp:80:2: note: in expansion of macro 'debug'
   80 |  debug();
      |  ^~~~~

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