Submission #1238534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238534		dosts	Sky Walking (IOI19_walk)	C++20	24 / 100	4067 ms	604580 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 5e6+1, inf = 2e18;

map<pii,int> id;
int gg = 0;
int node(int x,int y) {
	if (id.count({x,y})) return id[{x,y}];
	return id[{x,y}] = ++gg;
}
vector<pii> edges[LIM];
vi dist(LIM);


struct ST {
	vi t;

	ST(int nn) {
		t.assign(4*nn+1,0);
	}

	void update(int node,int l,int r,int p,int v) {
		if (l == r) {
			t[node] = v;
			return;
		}
		int m = (l+r) >> 1;
		if (p <= m) update(2*node,l,m,p,v);
		else update(2*node+1,m+1,r,p,v);
		t[node] = max(t[2*node],t[2*node+1]);
	}
	int walk(int node,int l,int r,int x) {
		if (t[node] < x) return -1;
		if (l == r) return l;
		int m = (l+r) >> 1;
		int v = walk(2*node,l,m,x);
		if (v!=-1) return v;
		return walk(2*node+1,m+1,r,x);
	}
	int query(int node,int l,int r,int L,int R,int x) {
		if (l > R || r < L) return -1;
		if (l >= L && r <= R) return walk(node,l,r,x);
		int m = (l+r) >> 1;
		int v = query(2*node,l,m,L,R,x);
		if (v == -1) return query(2*node+1,m+1,r,L,R,x);
		return v;
	}
};
int min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	int n = big(x);
	for (int i = 0;i<n;i++) node(x[i],0),node(x[i],h[i]);
	int m = big(l);
	ST st(n);
	for (int i=1;i<=n;i++) st.update(1,1,n,i,h[i-1]);
	for (int i = 0;i<m;i++) {
		int px = x[l[i]];
		int cur = l[i];
		while (cur != r[i]) {
			int nxt = st.query(1,1,n,cur+2,n,y[i])-1;
			int a = node(px,y[i]);
			int b = node(x[nxt],y[i]);
			edges[a].push_back({b,x[nxt]-px});
			edges[b].push_back({a,x[nxt]-px});
			px = x[nxt];
			cur = nxt;
		}
	}
	for (int i = 0;i<n;i++) {
		auto it = id.lower_bound({x[i],0});
		while (it != id.end() && next(it) != id.end() && next(it)->ff.ff == it->ff.ff) {
			int a = node(it->ff.ff,it->ff.ss),b = node(it->ff.ff,next(it)->ff.ss),c = next(it)->ff.ss-it->ff.ss;
			edges[a].push_back({b,c});
			edges[b].push_back({a,c});
			it = next(it);
		}
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,node(x[s],0)});
	dist.assign(gg+1,inf);
	dist[node(x[s],0)] = 0;
	while (!pq.empty()) {
		auto [cost,city] = pq.top();
		pq.pop();
		if (dist[city] != cost) continue;
		for (auto it : edges[city]) {
			if (dist[it.ff] > cost+it.ss) {
				dist[it.ff] = cost+it.ss;
				pq.push({cost+it.ss,it.ff});
			}
		}
	}
	if (dist[node(x[g],0)] < inf) return dist[node(x[g],0)];
	return -1;
}

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