Submission #285459

#	Time	Username	Problem	Language	Result	Execution time	Memory
285459		user202729	Sky Walking (IOI19_walk)	C++17	100 / 100	1312 ms	67384 KiB

walk

// moreflags=grader.cpp

// aren't the test cases for subtask 1 not strong enough?

// 14

#ifndef LOCAL
#define NDEBUG 1
#endif
//#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<map>
#include<cstdint>
#include<cassert>
#include<algorithm>
#include<climits>

#include "walk.h"

struct Value{
	std::set<int> have; //{y}
	std::map<int, int64_t> value;
	std::set<int> unstable;

	Value(){
		have.insert(0);
		value[0]=0;
	}

	void smoothen(int const curHeight){
		while(not unstable.empty()){ // smoothen part <= curHeight
			auto const pos=*unstable.begin();
			if(pos>curHeight) break;

			unstable.erase(unstable.begin());
			auto const iterator=value.find(pos);
			while(iterator!=value.begin()){
				auto const prev=std::prev(iterator);
				if(prev->second > iterator->second+iterator->first-prev->first)
					value.erase(prev);
				else
					break;
			}
		}

		if(auto const iterator=value.upper_bound(curHeight);
				iterator!=value.end()) unstable.insert(iterator->first);
	}

	void addOpen(int y, int curHeight){
		auto const [haveIterator, haveInserted]=have.insert(y);
		assert(haveInserted);

		auto const [iterator, inserted]=value.insert({y, 0});
		assert(inserted);
		int64_t curValue=INT64_MAX/2;
		if(iterator!=value.begin()){
			auto [y_, value1]=*std::prev(iterator);
			assert(y_<y);
			curValue=y-y_+value1;
		}
		if(std::next(iterator)!=value.end()){
			auto [y_, value1]=*std::next(iterator);
			//if(y_<=curHeight)
			if(*std::next(haveIterator)<=curHeight)
				curValue=std::min(curValue, y_-y+value1);
		}
		iterator->second=curValue;
	}

	void addClose(int y){
		auto const curHave=have.erase(have.find(y));
		auto curValue=value.find(y);
		if(curValue!=value.end()){
			auto const curValue_=curValue->second;
			auto const nextValue=value.erase(curValue);
			if(curHave!=have.begin()){
				auto const prevHave=std::prev(curHave);
				auto const newValue_=curValue_+y-*prevHave;

				auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
				// do nothing if *prevHave already exists in value
			}
		}
		assert(not unstable.count(y));
	}

	int64_t get(int pos)const{
		assert(have.count(pos));
		auto const [pos_, value_]=*value.lower_bound(pos);
		return value_+pos_-pos;
	}

	int64_t getLoose(int pos, int curHeight){
		// terrible and slow implementation...?
		assert(pos<=curHeight);
		bool const add=not have.count(pos);
		if(add) addOpen(pos, curHeight);
		auto const result=get(pos);
		if(add) addClose(pos);
		return result;
	}

	static void minimize(int y, std::array<Value, 2>& value, std::array<int, 2> const offset){
		// also kinda terrible and slow implementation
		std::array<bool, 2> add{};
		std::array<int64_t, 2> value_;
		for(int index=0; index<2; ++index){
			if(not value[index].have.count(y)){
				value[index].addOpen(y, y);
				add[index]=true;
			}

			value_[index]=value[index].get(y);
		}
		for(int index=0; index<2; ++index){
			if(auto const value1=2*offset[not index]+value_[not index]; value1<value_[index]){
				auto& cur=value[index];
				cur.value[y]=value1;
				assert(cur.unstable.empty() or *cur.unstable.begin()>y);
				cur.unstable.insert(cur.unstable.begin(), y);
				assert(*cur.unstable.begin()==y);
				cur.smoothen(y);
				assert(cur.unstable.empty() or *cur.unstable.begin()>y);
			}
		}
		for(int index=0; index<2; ++index){
			if(add[index])
				value[index].addClose(y);
		}
	}
};

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) {
	if(s>g) std::swap(s, g);

	struct Segment{ int left, right; };

	std::array<std::map<int, std::vector<Segment>>, 3> parts;
	std::array<std::vector<std::pair<int, Segment>>, 2> tops;
	auto const splitSegments=[&](bool keepParts){ // split segments into parts and tops
		std::map<int, std::vector<Segment>> segments;
		for(int index=0; index<(int)y.size(); ++index)
			segments[y[index]].push_back({l[index], r[index]});

		for(auto& it: tops) it.clear();
		for(auto& it: parts) it.clear();


		std::set<int> remaining;
		std::vector<std::pair<int, int>> heights(x.size());
		for(int it=0; it<(int)x.size(); ++it){
			remaining.insert(remaining.end(), it);
			heights[it]={h[it], it};
		}
		std::sort(begin(heights), end(heights),[&](auto first, auto sec){return first.first>sec.first;});

		for(auto& [y, it]: segments){
			while(not heights.empty() and heights.back().first<y){
				remaining.erase(remaining.find(heights.back().second));
				heights.pop_back();
			}

			assert(not it.empty());
			std::sort(begin(it), end(it),[&](auto first, auto sec){return first.left<sec.left;});
			auto out=++it.begin();
			std::for_each(out, it.end(),[&](auto segment){
				assert(out[-1].right<=segment.left);
				assert(segment.left<segment.right);
				if(out[-1].right==segment.left)
					out[-1].right=segment.right;
				else
					*out++=segment;
			});
			it.erase(out, it.end());

			for(auto [left, right]: it){
				assert(remaining.count(left));
				assert(remaining.count(right));
				assert(left<right);

				for(int i=0; i<2; ++i){
					if(left==right) break;
					auto const cut=i==0 ? s: g;
					if(i==1) assert(left>=s);
					if(left<right and left<cut){
						auto iterator=remaining.upper_bound(cut);
						auto const right1=right<=cut ? right: *std::prev(iterator);
						assert(left<=right1);
						if(left<right1){
							if(keepParts)
								parts[i][y].push_back({left, right1});
							left=right1;
						}

						if(left<right and left<cut){
							if(i==1){
								assert(left>=s); assert(*iterator>g);
							}
							tops[i].push_back({y, {left, *iterator}});
							left=*iterator;
							assert(left<=right);
						}
					}
				}

				assert(left<=right);
				if(left<right){
					assert(left>=g);
					if(keepParts)
						parts[2][y].push_back({left, right});
					left=right;
				}
			}
		}

		for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
					[&](auto first, auto sec){return first.first<sec.first;}));
	};
	splitSegments(false);


	{ // remap so that each top endpoint has a distinct x index
		std::vector<std::vector<int>> addLeft(x.size()), addRight(x.size());
		for(auto const& it: tops)
			for(auto [y, leftRight]: it){
				addRight[leftRight.left].push_back(y);
				addLeft[leftRight.right].push_back(y);
			}

		std::vector<int> map(x.size());
		std::vector<int> newx, newHeight;

		for(int index=0; index<(int)x.size(); ++index){
			std::sort(begin(addLeft[index]), end(addLeft[index]));
			std::sort(begin(addRight[index]), end(addRight[index]), std::greater<>());
			auto const curx=x[index], curHeight=h[index];
			for(auto height: addLeft[index]){
				assert(height<=curHeight);
				newx.push_back(curx); newHeight.push_back(height);
			}
			map[index]=(int)newx.size();
			newx.push_back(curx); newHeight.push_back(curHeight);
			for(auto height: addRight[index]){
				assert(height<=curHeight);
				newx.push_back(curx); newHeight.push_back(height);
			}
		}

		x=std::move(newx);
		h=std::move(newHeight);
		s=map[s]; g=map[g];
		for(auto& it: l) it=map[it];
		for(auto& it: r) it=map[it];
	}

	splitSegments(true);
	y.clear(); l.clear(); r.clear();

	struct Query{int pos, y;};
	std::vector<Query> queries;
	std::vector<int> distances;
	for(auto const& it: tops)
		for(auto [y, leftRight]: it){
			queries.push_back({leftRight.left, y});
			queries.push_back({leftRight.right, y});
			distances.push_back(x[leftRight.right]-x[leftRight.left]);
		}
	queries.push_back({s, 0});
	queries.push_back({g, 0});
	for(auto [pos, y]: queries) assert(y<=h[pos]);
	std::vector<std::array<int64_t, 2>> queryResult(queries.size(), {INT64_MAX/2, INT64_MAX/2});

	tops[0].push_back({INT_MAX, {0, (int)x.size()-1}});

	for(auto [y, leftRight]: tops[0])
		if(leftRight.right>g){
			assert(leftRight.left<s);
			tops[1].push_back({y, leftRight});
		}


	enum class Type{ open, query, close };
	struct Event{ int y, index; Type type; int queryIndex; };
	for(int index0=0; index0<2; ++index0){
		std::array<std::vector<Event>, 2> events;
		auto const start=index0==0 ? s: g;

		for(int queryIndex=0; queryIndex<(int)queries.size(); ++queryIndex){
			auto const [pos, y]=queries[queryIndex];
			if(pos<start) events[0].push_back({y, pos, Type::query, queryIndex});
			else if(pos>start) events[1].push_back({y, pos, Type::query, queryIndex});
			else queryResult[queryIndex][index0]=y;
		}

		for(auto const& [y, it]: parts[1+index0]){
			for(auto const it: it){
				assert(it.left>=start);
				events[1].push_back({y, it.left, Type::open});
				events[1].push_back({y, it.right, Type::close});
			}
		}
		events[1].push_back({0, start, Type::close});
		//events[1].push_back({0, g, Types::open});
		std::sort(begin(events[1]), end(events[1]),[&](Event first, Event sec){
			return first.index!=sec.index ? first.index>sec.index: first.type>sec.type;
			// reverse(increasing index->increasing type)
		});


		for(auto const& [y, it]: parts[0+index0]){
			for(auto const it: it){
				assert(it.right<=start);
				events[0].push_back({y, it.right, Type::open});
				events[0].push_back({y, it.left, Type::close});
			}
		}
		events[0].push_back({0, start, Type::close});
		//events[0].push_back({0, 0, Type::open});
		std::sort(begin(events[0]), end(events[0]),[&](Event first, Event sec){
			return first.index!=sec.index ? first.index<sec.index: first.type>sec.type;
			// reverse(decreasing index->increasing type)
		});

		auto const process1=[&](Value& value, int const index, std::vector<Event>& events){ // Type::open
			auto const curHeight=h[index];
			value.smoothen(curHeight);

			while(not events.empty() and events.back().index==index){
				auto const [y, index_, type, _]=events.back();
				assert(index==index_);
				assert(y<=curHeight);
				if(type==Type::open){
					value.addOpen(y, curHeight);
				}else{
					return;
				}
				events.pop_back();
			}
		};

		auto const process2=[&](Value& value, int const index, std::vector<Event>& events, int const offset){ // Type::{query, close}
			auto const curHeight=h[index];
			while(not events.empty() and events.back().index==index){
				auto const [y, index_, type, queryIndex]=events.back();
				assert(index==index_);
				assert(y<=curHeight);
				if(type==Type::close){
					value.addClose(y);
				}else{
					assert(type==Type::query);
					queryResult[queryIndex][index0]=value.getLoose(y, curHeight)+offset;
				}
				events.pop_back();
			}
		};

		std::array<int, 2> bounds{{start, start}};
		std::array<Value, 2> value;
		process1(value[0], start, events[0]);
		process1(value[1], start, events[1]);
		process2(value[0], start, events[0], 0);
		process2(value[1], start, events[1], 0);

		for(auto const [y, leftRight]: tops[index0]){
			auto const [left, right]=leftRight;

			assert(bounds[0]>=left);
			while(bounds[0]>left){
				process1(value[0], --bounds[0], events[0]);
				if(bounds[0]>left)
					process2(value[0], bounds[0], events[0], x[start]-x[bounds[0]]);
			}
			assert(bounds[1]<=right);
			while(bounds[1]<right){
				process1(value[1], ++bounds[1], events[1]);
				if(bounds[1]<right)
					process2(value[1], bounds[1], events[1], x[bounds[1]]-x[start]);
			}

			std::array<int, 2> const offset{{x[start]-x[left], x[right]-x[start]}};
			Value::minimize(y, value, offset);
			process2(value[0], bounds[0], events[0], offset[0]);
			process2(value[1], bounds[1], events[1], offset[1]);
		}
	}

	int64_t result=INT64_MAX;
	for(auto [a, b]: queryResult){
		if(a<INT64_MAX/2 and b<INT64_MAX/2)
			result=std::min(result, a+b);
	}
	for(int index=0; index<(int)distances.size(); ++index){
		auto const [a, b]=queryResult[index*2];
		auto const [c, d]=queryResult[index*2+1];
		if(a<INT64_MAX/2 and d<INT64_MAX/2)
			result=std::min(result, a+d+distances[index]);
		if(b<INT64_MAX/2 and c<INT64_MAX/2)
			result=std::min(result, b+c+distances[index]);
	}
	return result==INT64_MAX ? -1: result;
}

Compilation message (stderr)

walk.cpp: In member function 'void Value::addClose(int)':
walk.cpp:82:16: warning: variable 'newValueIterator' set but not used [-Wunused-but-set-variable]
   82 |     auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
      |                ^~~~~~~~~~~~~~~~
walk.cpp: In lambda function:
walk.cpp:219:13: warning: unused variable 'it' [-Wunused-variable]
  219 |   for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
      |             ^~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:273:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  273 |  for(auto [pos, y]: queries) assert(y<=h[pos]);
      |           ^~~~~~~~

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