Submission #283863

#	Time	Username	Problem	Language	Result	Execution time	Memory
283863		user202729	Sky Walking (IOI19_walk)	C++17	33 / 100	746 ms	51296 KiB

walk

// moreflags=grader.cpp






// 17

#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>

#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));
	}

	static void minimize(int y, Value& first, Value& sec, int offset1, int offset2){
	}
};

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) {
	//int64_t result=INT64_MAX;

	if(s>g) std::swap(s, g);
	auto const n=(int)x.size();

	struct Segment{
		int left, right;
	};
	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]});

	std::array<std::map<int, std::vector<Segment>>, 3> parts;
	std::array<std::vector<std::pair<int, Segment>>, 2> tops;
	std::set<int> remaining;
	std::vector<std::pair<int, int>> heights(n);
	for(int it=0; it<n; ++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){
						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);
				parts[2][y].push_back({left, right});
				left=right;
			}
		}
	}

	tops[0].push_back({INT_MAX, {0, n-1}});
	for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
				[&](auto first, auto sec){return first.first<sec.first;}));

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



	enum class Type{ open, close };
	struct Event{ int y, index; Type type; };
	std::array<std::vector<Event>, 2> events;


	for(auto const& [y, it]: parts[1]){
		for(auto const it: it){
			events[1].push_back({y, it.left, Type::open});
			events[1].push_back({y, it.right, Type::close});
		}
	}
	events[1].push_back({0, s, Type::close});
	events[1].push_back({0, g, Type::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->open before close)
	});


	for(auto const& [y, it]: parts[0]){
		for(auto const it: it){
			events[0].push_back({y, it.right, Type::open});
			events[0].push_back({y, it.left, Type::close});
		}
	}
	events[0].push_back({0, s, 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->open before close)
	});

	/*
	std::array<int, 2> bounds{{s, s}};
	std::array<Value, 2> value;

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

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

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

		assert(bounds[0]>=left);
		while(bounds[0]>left){
			process(value[0], --bounds[0], events[0]);
		}
		assert(bounds[1]<=right);
		while(bound[1]<right){
			process(value[1], ++bounds[1], events[1]);
		}


		Value::minimize(y, value[0], value[1], x[s]-x[left], x[right]-x[s]);
	}

	for(int index=0; index<(int)x.size();++index){
	}
	*/




	if(s==0 and g==n-1){
		std::vector<Event> events;
		for(auto const& [y, it]: segments){
			for(auto const it: it){
				events.push_back({y, it.left, Type::open});
				events.push_back({y, it.right, Type::close});
			}
		}
		events.push_back({0, 0, Type::close});
		events.push_back({0, n-1, Type::open});
		std::sort(begin(events), end(events),[&](Event first, Event sec){
			return first.index!=sec.index ? first.index>sec.index: first.type>sec.type;
			// reverse(increasing index->open before close)
		});

		Value value;
		for(int index=0; index<(int)x.size();++index){
			auto const curHeight=h[index];
			value.smoothen(curHeight);

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

		assert(value.value.size()==1);
		assert(value.value.begin()->first==0);
		auto const result=value.value.begin()->second+(x.back()-x[0]);

		return result>=INT64_MAX/2 ? -1: result;
	}

	__builtin_trap();
}

Compilation message (stderr)

walk.cpp: In member function 'void Value::addClose(int)':
walk.cpp:78:16: warning: variable 'newValueIterator' set but not used [-Wunused-but-set-variable]
   78 |     auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
      |                ^~~~~~~~~~~~~~~~
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:171:12: warning: unused variable 'it' [-Wunused-variable]
  171 |  for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
      |            ^~

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