Submission #261251

#	Time	Username	Problem	Language	Result	Execution time	Memory
261251		user202729	Palembang Bridges (APIO15_bridge)	C++17	41 / 100	2064 ms	9320 KiB

bridge

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

struct Function{
	std::vector<int> changes; // by 2, must be even
	std::vector<int64_t> value;
	int64_t value0{};
	void add(std::pair<int, int> it){
		changes.push_back(it.first);
		changes.push_back(it.second);
		assert(it.first<=it.second);
		value0+=2*(0<it.first ? it.first-0: 0>it.second ? 0-it.second: 0);
	}
	void build(){
		std::sort(begin(changes), end(changes));
		assert(value.empty());
		if(changes.empty()) {
			assert(value0==0);
			return;
		}
		value.resize(changes.size());
		int slope=-(int)changes.size();
		value[0]=0;
		for(int index=1; index<(int)changes.size(); ++index){
			slope+=2;
			value[index]=value[index-1]+slope*int64_t(changes[index]-changes[index-1]);
		}
		slope+=2;
		assert(slope==(int)changes.size());

		auto const delta=value0-calculate(0);
		for(auto& it: value) it+=delta;
		assert(calculate(0)==value0);
	}
	int64_t calculateTwice(int64_t twicePos) const{
		assert(changes.size()%2==0);
		if(changes.empty()) {
			assert(value0==0);
			return 0;
		}

		auto index=int(std::lower_bound(begin(changes), end(changes), (twicePos+1)>>1)-begin(changes));
		if(index==(int)changes.size()){
			return value.back()+int64_t(changes.size()/2)*(twicePos-changes.back()*2);
		}else{
			return value[index]-int64_t(changes[index]*2-twicePos)*(index-int64_t(changes.size()/2));
		}
	}
	int64_t calculate(int64_t pos){return calculateTwice(pos*2);}
	int minPos() const{
		assert(changes.size()%2==0);
		return changes.empty() ? 0: changes[changes.size()/2];
	}

	// a(x), b(x) -> (x -> a(x)+b(x))
	template<bool flip=false>
	Function add(Function const& other) const{
		Function result;
		for(auto it: changes) result.changes.push_back(it);
		for(auto it: other.changes) result.changes.push_back(flip ? -it: it);
		result.value0=value0+other.value0;
		result.build();
		return result;
	}
	// a(x), b(x) -> (x -> a(x)+b(-x))
	Function addFlipSecond(Function const& other) const{
		return add<true>(other);
	}
};

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int numBridge, numPeople; std::cin>>numBridge>>numPeople;
	int64_t base{};
	std::vector<std::pair<int, int>> terms; terms.reserve(numPeople);
	for(int _=0; _<numPeople; ++_){
		char side1, side2; int pos1, pos2;
		std::cin>>side1>>pos1>>side2>>pos2;
		std::tie(pos1, pos2)=std::minmax({pos1, pos2});
		if(side1==side2) base+=pos2-pos1;
		else {
			base+=pos2-pos1+1;
			terms.push_back({pos1, pos2});
		}
	}
	assert((int)terms.size()<=numPeople);
	if(terms.empty()){std::cout<<base<<'\n'; return 0;}

	std::vector<int> positions; positions.reserve(terms.size()*2);
	for(auto [first, sec]: terms){
		positions.push_back(first); positions.push_back(sec);
	}
	std::sort(begin(positions), end(positions));
	positions.erase(std::unique(begin(positions), end(positions)), end(positions));

	/*
	auto const calculate=[&](int pos){
		int64_t result{};
		for(auto [first, sec]: terms){
			if(pos<first) result+=first-pos;
			else if(pos>sec) result+=pos-sec;
		}
		return result*2;
	};

	if(numBridge==1){
		int index=0; auto curValue=calculate(positions[0]);
		for(int step=1<<30; step>>=1;){
			auto const check=[&](int next){
				if((unsigned) next<positions.size()){
					auto const nextValue=calculate(positions[next]);
					if(nextValue<curValue){index=next; curValue=nextValue;}
				}
			};
			check(index-step); check(index+step);
		}
		std::cout<<curValue+base<<'\n';
	}
	*/

	auto const center=[&](auto it){return it.first+it.second;};
	if(numBridge==2){
		std::sort(begin(terms), end(terms),[&](auto first, auto sec){
			return center(first)<center(sec);
		});
		auto result=INT64_MAX;
		for(int index=0; index<=(int)terms.size(); ++index){
			int twicedleft=index==0 ? INT_MIN: center(terms[index-1]);
			int twicedright=index==(int)terms.size() ? INT_MAX: center(terms[index]);
			// consider d in [twicedleft/2..twicedright/2]
			// left terms=(0..index), right terms=(index..(int)terms.size())
			
			Function sumFunction, diffFunction;
			for(int i=0; i<index; ++i)
				diffFunction.add(terms[i]);
			for(int i=index; i<(int)terms.size(); ++i)
				sumFunction.add(terms[i]);
			sumFunction.build();
			diffFunction.build();

			auto sum1=sumFunction.minPos(), diff1=diffFunction.minPos(); // d+r, d-r
			auto twiced=sum1+diff1, twicer=sum1-diff1;
			if(twicer>=0 and twicedleft<=twiced and twiced<=twicedright){
				result=std::min(result, sumFunction.calculate(sum1)+diffFunction.calculate(diff1));
			}
			else if(twicer<0){
				// in this branch, sometimes it's not necessary to binary search...
				Function functionr0=sumFunction.add(diffFunction); // d -> value|d=d, r=0
				auto const twiced=std::max((int64_t)twicedleft,
						std::min((int64_t)twicedright, (int64_t)functionr0.minPos()*2));
				result=std::min(result, sumFunction.calculateTwice(twiced)+diffFunction.calculateTwice(twiced));
			}
			else if(twiced<twicedleft){
				Function f=sumFunction.addFlipSecond(diffFunction);
				auto const twicer=std::max<int64_t>(0, twicedleft+(int64_t)f.minPos()*2);
				result=std::min(result, sumFunction.calculateTwice(twicedleft+twicer)+
						diffFunction.calculateTwice(twicedleft-twicer));
			}
			else if(twiced>twicedright){
				Function f=sumFunction.addFlipSecond(diffFunction);
				auto const twicer=std::max<int64_t>(0, twicedright+(int64_t)f.minPos()*2);
				result=std::min(result, sumFunction.calculateTwice(twicedright+twicer)+
						diffFunction.calculateTwice(twicedright-twicer));
			}

		}
		std::cout<<result+base<<'\n';
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37