제출 #284398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284398		user202729	Shortcut (IOI16_shortcut)	C++17	71 / 100	2073 ms	8568 KiB

shortcut

// moreflags=grader.cpp
// 16
#include "shortcut.h"
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdint>
#include<climits>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>


long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	std::vector<int64_t> pos; pos.reserve(n);
	pos.push_back(0);
	/*
	pos.insert(pos.end(), begin(l), end(l));
	std::partial_sum(++begin(pos), end(pos), ++pos.begin(), 0);
	*/
	std::inclusive_scan(begin(l), end(l), std::back_inserter(pos), std::plus<>(), (int64_t)0);

	int64_t result{};
	for(auto it: l) result+=it;
	result+=2**std::max_element(begin(d), end(d));
	l.clear();

	auto const check=[&](int64_t const result){
		auto const process=[&](int64_t initial, auto const f1, auto const f2){
			auto const c1=[&](int a){return d[a]-pos[a];};
			auto const c2=[&](int b){return +d[b]+pos[b];};

			enum class Type{query, set};
			struct Event{
				int64_t x; int y; Type type; int64_t value;
			};
			std::vector<Event> events; events.reserve(n*2-1);

			for(int a=0; a<n; ++a)
				events.push_back({result-c1(a), a+1, Type::query, f1(a)});
			for(int b=1; b<n; ++b)
				events.push_back({c2(b), b, Type::set, f2(b)});
			assert((int)events.size()==n*2-1);

			struct Tree{ // BIT.
				std::vector<int64_t> value;
				Tree(int number): value(number, INT64_MAX){}
				int64_t minSuffix(int pos) const{
					assert(pos>=0); // if pos is too large then INT64_MAX is returned
					int64_t result=INT64_MAX;
					while(pos<(int)value.size()){
						result=std::min(result, value[pos]);
						pos|=pos+1;
					}
					return result;
				}
				void setMinimum(int pos, int64_t value_){
					do{
						value[pos]=std::min(value[pos], value_);
						pos&=pos+1; --pos;
					}while(pos>=0);
				}
			};
			Tree tree(n);

			std::sort(begin(events), end(events),[&](Event first, Event sec){
				return first.x!=sec.x ? first.x>sec.x: first.type<sec.type;
			});
			for(auto const [_x, y, type, value]: events){
				if(type==Type::query){
					auto const tmp=tree.minSuffix(y);
					if(tmp!=INT64_MAX) initial=std::min(initial, tmp+value);
				}else{
					assert(type==Type::set);
					tree.setMinimum(y, value);
				}
			}

			return initial;
		};

		std::array<int64_t, 4> bounds;
		bounds[1]=process(INT64_MAX, [&](int a){return pos[a]-d[a]  ;}, [&](int b){return +pos[b]-d[b] ;});
		if(bounds[1]==INT64_MAX) return true; // no bound. (result >=old diameter)

		bounds[1]+=result-c;
		bounds[0]=c-result-process(0, [&](int a){return -d[a]-pos[a] ;}, [&](int b){return -d[b]-pos[b] ;});
		if(bounds[0]>bounds[1]) return false;

		bounds[2]=c-result-process(0, [&](int a){return -d[a]+pos[a] ;}, [&](int b){return -d[b]-pos[b] ;});
		bounds[3]=result-c+process(INT64_MAX, [&](int a){return -pos[a]-d[a] ;}, [&](int b){return +pos[b]-d[b] ;});
		if(bounds[2]>bounds[3]) return false;

		for(auto p: pos){
			auto const l=std::max(bounds[0]-p, bounds[2]+p), r=std::min(bounds[1]-p, bounds[3]+p);
			if(l<=r){
				auto const iterator=std::lower_bound(begin(pos), end(pos), l);
				if(iterator!=pos.end() and *iterator<=r)
					return true; // found a point
			}
		}
		return false;
	};

	for(int64_t step=(int64_t)1<<(63^__builtin_clzll(result)); step; step>>=1)
		if(result-step>0 and check(result-step))
			result-=step;
	return result;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3