제출 #838080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838080		penguinman	Sky Walking (IOI19_walk)	C++17	57 / 100	4091 ms	1008752 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

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

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);


template<typename T>
struct li_chao_tree{
	ll N;
	vector<std::pair<T,T>> lines;
	vector<T> x;
	std::map<ll,ll> rev;
	li_chao_tree(vector<T> X, T xINF){
		N = 1;
		while(N <= x.size()) N *= 2;
		lines.resize(2*N, mp(0,inf));
		x.resize(N);
		rep(i,0,N){
			if(i < X.size()){
				x[i] = X[i];
				rev[x[i]] = i;
			}
			else x[i] = xINF;
		}
	}
	ll ID(T X){
		return rev[X];
	}
	T value(std::pair<T,T> line, T X){
		return line.first*X+line.second;
	}
	void add_segment(ll a, ll b, std::pair<T,T> line, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		if(b <= l || r <= a) return;
		if(a <= l && r <= b){
			if(N <= now){
				if(value(lines[now], x[l]) > value(line, x[l])) lines[now] = line;
				return;
			}
			ll m = (l+r)/2;
			bool left = (value(lines[now],x[l]) < value(line, x[l]));
			bool mid = (value(lines[now],x[m]) < value(line, x[m]));
			bool right = (value(lines[now],x[r]) < value(line, x[r]));
			if(left && mid && right){
				std::swap(line, lines[now]);
				return;
			}
			if(!left && !mid && !right){
				return;
			}
			if(left && mid){
				std::swap(line, lines[now]);
				add_segment(a,b,line,now*2+1,m,r);
				return;
			}
			if(mid && right){
				std::swap(line, lines[now]);
				add_segment(a,b,line,now*2,l,m);
				return;
			}
			if(left){
				add_segment(a,b,line,now*2,l,m);
				return;
			}
			if(right){
				add_segment(a,b,line,now*2+1,m,r);
				return;
			}
		}
		else{
			add_segment(a,b,line,now*2,l,(l+r)/2);
			add_segment(a,b,line,now*2+1,(l+r)/2,r);
		}
	}
	T calc(ll idx, T X){
		T ret = inf;
		idx += N;
		while(idx){
			ret = std::min(idx, value(lines[idx], X));
			idx /= 2;
		}
		return ret;
	}
};

template<typename T>
struct segment_tree{
	ll N;
	vector<T> node;
	T valINF;
	segment_tree(int n, T valINF_): valINF(valINF_){
		N = 1;
		while(N <= n) N *= 2;
		node.resize(2*N, valINF);
	}
	void set(ll idx, T val){
		idx += N;
		node[idx] = val;
		idx /= 2;
		while(idx){
			node[idx] = compare(node[idx*2], node[idx*2+1]);
			idx /= 2;
		}
	}
	T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		if(b <= l || r <= a) return valINF;
		if(a <= l && r <= b) return node[now];
		return compare(calc(a,b,now*2,l,(l+r)/2), calc(a,b,now*2+1,(l+r)/2,r));
	}
	T compare(T l, T r){
		return std::min(l, r);
	}
};

void dec(std::map<ll,ll> &map, ll el){
	map[el]--;
	if(map[el] == 0) map.erase(el);
}


ll solve_subtask_1_2(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){
	ll N = x.size();
	segment_tree<pii> seg(N,mp(inf,inf));

	vii edge(N), weight(N);
	vector<std::map<ll,ll>> rev(N);
	rep(i,0,N) rev[i][0] = i;

	ll K = N;

	rep(i,0,N) seg.set(i, mp(-h[i], i));

	rep(i,0,l.size()){
		vi data;
		while(true){
			auto el = seg.calc(l[i], r[i]+1);
			if(-el.first < y[i]) break;
			data.pb(el.second);
			seg.set(el.second, mp(inf, inf));
		}
		sort(all(data));
		for(auto el: data){
			if(!rev[el].count(y[i])){
				rev[el][y[i]] = K++;
				weight.pb(vi());
				edge.pb(vi());
			}
		}
		rep(j,1,data.size()){
			ll now = rev[data[j-1]][y[i]];
			ll next = rev[data[j]][y[i]];
			edge[now].pb(next);
			edge[next].pb(now);
			ll cost = x[data[j]]-x[data[j-1]];
			weight[now].pb(cost);
			weight[next].pb(cost);
		}
		for(auto el: data){
			seg.set(el, mp(-h[el], el));
		}
	}

	rep(i,0,N){
		vi data, height;
		for(auto el: rev[i]){
			data.pb(el.second);
			height.pb(el.first);
		}
		rep(j,1,data.size()){
			ll now = data[j-1];
			ll next = data[j];
			edge[now].pb(next);
			edge[next].pb(now);
			ll cost = height[j]-height[j-1];
			weight[now].pb(cost);
			weight[next].pb(cost);
		}
	}

	std::priority_queue<pii> que;
	vi dist(K, inf);
	dist[rev[s][0]] = 0;
	que.push(mp(0,rev[s][0]));
	while(!que.empty()){
		auto el = que.top(); que.pop();
		ll now = el.second;
		if(dist[now] < -el.first) continue;
		rep(i,0,edge[now].size()){
			ll next = edge[now][i];
			ll sum = dist[now]+weight[now][i];
			if(sum < dist[next]){
				dist[next] = sum;
				que.push(mp(-sum, next));
			}
		}
	}
	ll ans = dist[rev[g][0]];
	if(ans == inf) ans = -1;
	return ans;
}

ll solve_subtask_3_4(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){
	ll N = x.size();
	vi y_mem;
	std::map<ll,ll> mem;
	ll M = 0;
	{
		mem[0] = 0;
		for(auto el: h) mem[el] = 0;
		for(auto el: y) mem[el] = 0;
		for(auto &el: mem){
			y_mem.pb(el.first);
			el.second = M++;
		}
	}

	segment_tree<ll> left(M, inf), right(M, inf);

	vector<std::map<ll,ll>> value(M);
	rep(i,0,M) value[i][inf] = 1;

	vii erase_idx(N), erase_val(N);

	vii add(N);
	rep(i,0,l.size()){
		add[l[i]].pb(i);
	}

	rep(t,0,N){
		for(auto i: add[t]){
			ll val = left.calc(0, mem[y[i]]+1)+y[i];
			val = std::min(val, right.calc(mem[y[i]], M)-y[i]);
			if(t == 0) val = y[i];
			value[mem[y[i]]][val]++;
			left.set(mem[y[i]], (*value[mem[y[i]]].begin()).first-y[i]);
			right.set(mem[y[i]], (*value[mem[y[i]]].begin()).first+y[i]);
			erase_idx[r[i]].pb(y[i]);
			erase_val[r[i]].pb(val);
		}
		if(t == N-1) break;
		rep(i,0,erase_idx[t].size()){
			ll Y = erase_idx[t][i];
			ll V = erase_val[t][i];
			dec(value[mem[Y]], V);
			left.set(mem[Y], (*value[mem[Y]].begin()).first-Y);
			right.set(mem[Y], (*value[mem[Y]].begin()).first+Y);
		}
	}
	ll ans = right.calc(0,M)+x[N-1]-x[0];
	if(ans >= inf/2) ans = -1;
	return ans;
}

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) {
	ll N = x.size();
	if(s == 0 && g == N-1) return solve_subtask_3_4(x,h,l,r,y,s,g);
	return solve_subtask_1_2(x,h,l,r,y,s,g);
}

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