Submission #283636

#	Time	Username	Problem	Language	Result	Execution time	Memory
283636		user202729	Sky Walking (IOI19_walk)	C++17	15 / 100	428 ms	32744 KiB

walk

// moreflags=grader.cpp
// what have I done...
// :(






// 17

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

#include "walk.h"

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;

	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]});
	for(auto& [_y, it]: segments){
		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());
	}

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

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

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

		have.insert(0);
		value[0]=0;

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

			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=have.upper_bound(curHeight);
					iterator!=have.end()) unstable.insert(*iterator);

			while(not events.empty() and events.back().index==index){
				auto const [y, index_, open]=events.back(); events.pop_back();
				assert(index==index_);
				assert(y<=curHeight);
				if(open){
					{
						auto const [iterator, inserted]=have.insert(y);
						assert(inserted);
					}
					{
						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)
								curValue=std::min(curValue, y_-y+value1);
						}
						iterator->second=curValue;
					}
				}else{
					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
						}
					}
				}
			}
		}

		auto const result=(value.empty() ? INT64_MAX/2: value.begin()->first+value.begin()->second)
			+x.back()-x[0];
		return result>=INT64_MAX/2 ? -1: result;
	}
	__builtin_trap();
	//return (result==INT64_MAX ? -1: result);
}

Compilation message (stderr)

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:97:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   97 |       auto const [iterator, inserted]=have.insert(y);
      |                  ^~~~~~~~~~~~~~~~~~~~
walk.cpp:126:19: warning: variable 'newValueIterator' set but not used [-Wunused-but-set-variable]
  126 |        auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
      |                   ^~~~~~~~~~~~~~~~

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