제출 #838060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838060		penguinman	Sky Walking (IOI19_walk)	C++17	0 / 100	316 ms	32520 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);

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){

}

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;
	ll valINF;
	segment_tree(int n, ll 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_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]], mem[h[i]]+1)-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);
		}
	}
	return right.calc(0,M)+x[N-1]-x[0];
}

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 -1;
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'll solve_subtask_1_2(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
   30 | }
      | ^

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