Submission #615927

#	Time	Username	Problem	Language	Result	Execution time	Memory
615927		amunduzbaev	Sky Walking (IOI19_walk)	C++17	0 / 100	472 ms	141628 KiB

walk

#include "bits/stdc++.h"
using namespace std;
#include "walk.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
const ll inf = 2e18;
const int N = 1e5 + 5;

struct ST{
	vector<ll> tree;
	vector<ar<int, 2>> c;
	int last;
	void add(){
		tree.push_back(inf);
		c.push_back({});
		last++;
	}
	
	ST(){ add(); }
	
	void umin(int i, ll v, int lx = 0, int rx = N, int x = 0){
		if(lx == rx) {
			tree[x] = min(tree[x], v);
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m){
			if(!c[x][0]) c[x][0] = last, add();
			umin(i, v, lx, m, c[x][0]);
		} else {
			if(!c[x][1]) c[x][1] = last, add();
			umin(i, v, m + 1, rx, c[x][1]);
		}
		
		tree[x] = inf;
		if(c[x][0]) tree[x] = min(tree[x], tree[c[x][0]]);
		if(c[x][1]) tree[x] = min(tree[x], tree[c[x][1]]);
	}
	
	ll get(int l, int r, int lx = 0, int rx = N, int x = 0){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		ll res = inf;
		if(c[x][0]) res = min(res, get(l, r, lx, m, c[x][0]));
		if(c[x][1]) res = min(res, get(l, r, m + 1, rx, c[x][1]));
		
		return res;
	}
};

struct ST2{
	ST tree[N << 2];
	
	void umin(int i, int j, ll v, int lx = 0, int rx = N, int x = 1){
		tree[x].umin(j, v);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) umin(i, j, v, lx, m, x << 1);
		else umin(i, j, v, m + 1, rx, x << 1 | 1);
	}
	
	ll get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r){
			return tree[x].get(l_, r_);
		}
		
		int m = (lx + rx) >> 1;
		return min(get(l, r, l_, r_, lx, m, x << 1), get(l, r, l_, r_, m + 1, rx, x << 1 | 1));
	}
}add, sub;

vector<ar<int, 2>> edges[N * 11];
ll d[N * 11];

#define sow cout<<"here"<<endl;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size(), q = l.size();
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return r[i] < r[j];
	});
	
	vector<int> tot;
	vector<ll> dp(q, inf);
	for(int i=0;i<q;i++){
		tot.push_back(y[i]);
	}
	
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	ll res = inf;
	sub.umin(0, 0, 0);
	add.umin(0, 0, 0);
	for(auto i : p){
		if(y[i] > h[0]) continue;
		
		int j = lower_bound(tot.begin(), tot.end(), y[i]) - tot.begin() + 1;
		dp[i] = min(dp[i], sub.get(l[i], r[i], 0, j) + y[i]);
		dp[i] = min(dp[i], add.get(l[i], r[i], j, q) - y[i]);
		sub.umin(r[i], j, dp[i] - y[i]);
		add.umin(r[i], j, dp[i] + y[i]);
		if(r[i] == n - 1) res = min(res, dp[i]);
	}
	
	res += (x[n - 1] - x[0]);
	if(res < 1e18){
		return res;
	} else {
		return -1;
	}
}

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