Submission #1154624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154624		Pacybwoah	Sky Walking (IOI19_walk)	C++20	25 / 100	193 ms	27832 KiB

walk

#include "walk.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<queue>
typedef long long ll;
const ll inf = 1e16;
using namespace std;
struct BIT{
    vector<ll> bit;
    int n;
    BIT(int _n){
        n = _n;
        bit.resize(n + 1);
		fill(bit.begin(), bit.end(), inf);
    }
    void modify(int pos, ll val){
        while(pos <= n){
            bit[pos] = min(bit[pos], val);
            pos += (pos & -pos);
        }
    }
    int query(int pos){
     	ll ans = inf;
        while(pos > 0){
            ans = min(ans, bit[pos]);
            pos -= (pos & -pos);
        }
        return ans;
    }
};
struct st{
	vector<ll> seg;
	st(int n){
		seg.resize(4 * n + 4);
		fill(seg.begin(), seg.end(), inf);
	}
	void modify(int l, int r, int pos, ll num, int ind){
		if(l == r){
			seg[ind] = num;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(l, mid, pos, num, ind * 2);
		else modify(mid + 1, r, pos, num, ind * 2 + 1);
		seg[ind] = min(seg[ind * 2], seg[ind * 2 + 1]);
	}
	ll query(int l, int r, int start, int end, int ind){
		if(r < start || end < l) return inf;
		if(start <= l && r <= end) return seg[ind];
		int mid = (l + r) >> 1;
		return min(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
	}
};
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 g) {
	vector<ll> cp;
	int n = (int)x.size(), m = (int)l.size();
	for(int i = 0; i < n; i++) cp.push_back(h[i]);
	for(int i = 0; i < m; i++) cp.push_back(y[i]);
	cp.push_back(0);
	sort(cp.begin(), cp.end());
	cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
	for(auto &xx: h){
		xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
	}
	for(auto &xx: y){
		xx = lower_bound(cp.begin(), cp.end(), xx) - cp.begin() + 1;
	}
	vector<vector<int>> in(n), out(n);
	for(int i = 0; i < m; i++){
		in[l[i]].push_back(i);
		out[r[i]].push_back(i);
	}
	int sz = (int)cp.size();
	if(n > 50 && m > 50){
		// cp[pos - 1]
		st cis(sz);
		st trans(sz);
		cis.modify(1, sz, 1, 0, 1);
		trans.modify(1, sz, 1, 0, 1);
		cp.insert(cp.begin(), 0);
		for(int i = 0; i < n; i++){
			vector<ll> dps((int)in[i].size());
			int cnt = 0;
			for(auto &id: in[i]){
				ll dp = inf;
				dp = min(dp, cis.query(1, sz, 1, y[id], 1) + cp[y[id]]);
				if(h[i] > y[id]) dp = min(dp, trans.query(1, sz, y[id], h[i], 1) - cp[y[id]]);
				dps[cnt] = dp;
				cnt++;
			}
			if(i < n - 1) for(auto &id: out[i]){
				cis.modify(1, sz, y[id], inf, 1);
				trans.modify(1, sz, y[id], inf, 1);
			}
			if(i == 0){
				cis.modify(1, sz, 1, inf, 1);
				trans.modify(1, sz, 1, inf, 1);
			}
			cnt = 0;
			for(auto &id: in[i]){
				cis.modify(1, sz, y[id], dps[cnt] - cp[y[id]], 1);
				trans.modify(1, sz, y[id], dps[cnt] + cp[y[id]], 1);
				cnt++;
			}
		}
		ll ans = inf;
		for(int i = 1; i <= h[n - 1]; i++){
			ans = min(ans, cis.query(1, sz, i, i, 1) + cp[i] + cp[i]);
			ans = min(ans, trans.query(1, sz, i, i, 1));
			//cout << i << " " << cis.query(1, sz, i, i, 1) + cp[i] << " " << trans.query(1, sz, i, i, 1) - cp[i] << "\n";
		}
		if(ans == inf) return -1;
		return ans + x[n - 1] - x[0];
	}
	int cnt = 1;
	multiset<int> se;
	vector<vector<pair<int, ll>>> graph(1);
	vector<pair<int, int>> lst(sz + 1);
	cp.insert(cp.begin(), 0);
	int start = -1, end = -1;
	for(int i = 0; i < n; i++){
		vector<int> nodes;
		nodes.push_back(1);
		for(auto &id: in[i]){
			se.insert(y[id]);
		}
		auto iter = se.begin();
		while(iter != se.end() && (*iter) <= h[i]){
			nodes.push_back((*iter));
			iter = next(iter);
		}
		int szz = (int)nodes.size();
		for(int j = 0; j < szz; j++){
			graph.push_back({});
			//cout << cnt + j << " " << i << " " << nodes[j] << "\n";
		}
		for(int j = 0; j < szz - 1; j++){
			graph[cnt + j].emplace_back(cnt + j + 1, cp[nodes[j + 1]] - cp[nodes[j]]);
			graph[cnt + j + 1].emplace_back(cnt + j, cp[nodes[j + 1]] - cp[nodes[j]]);
		}
		for(int j = 1; j < szz; j++){
			if(lst[nodes[j]].first > 0){
				graph[lst[nodes[j]].first].emplace_back(cnt + j, x[i] - x[lst[nodes[j]].second]);
				graph[cnt + j].emplace_back(lst[nodes[j]].first, x[i] - x[lst[nodes[j]].second]);
			}
			lst[nodes[j]] = make_pair(cnt + j, i);
		}
		if(s == i) start = cnt;
		if(g == i) end = cnt;
		cnt += szz;
		for(auto &id: out[i]){
			se.erase(se.find(y[id]));
			if(se.count(y[id]) == 0) lst[y[id]] = make_pair(0, 0);
		}
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<ll> dist(cnt + 1, inf);
	dist[start] = 0;
	pq.emplace(0, start);
	while(!pq.empty()){
		auto [d, node] = pq.top();
		pq.pop();
		if(d != dist[node]) continue;
		for(auto &[v, le]: graph[node]){
			if(d + le < dist[v]){
				dist[v] = d + le;
				pq.emplace(d + le, v);
			}
		}
	}
	/*for(int i = 1; i < cnt; i++){
		for(auto &[lll, xx]: graph[i]) cout << i << " " << lll << " " << xx << "\n";
	}*/
	//cout << start << " " << end << "\n";
	if(dist[end] == inf) return -1;
	return dist[end];
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp walk.cpp

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