Submission #261346

#	Time	Username	Problem	Language	Result	Execution time	Memory
261346		user202729	Palembang Bridges (APIO15_bridge)	C++17	41 / 100	36 ms	2688 KiB

bridge

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


template <class Node, class Detail>struct SegmentTreeTemplate{std::vector<Node> data;SegmentTreeTemplate(){}SegmentTreeTemplate(int number){assign(number);}SegmentTreeTemplate(std::size_t number){assign(number);}SegmentTreeTemplate(int number,Node const& node){assign(number,node);}void assign(int number){assign(number,Node{});}void assign(int number,Node const& node){assign(number,[&]{return node;});}void assign(int number,auto const& generator){data.reserve(number*2);data.resize(number);for(int i=0;i<number;++i) {if(data.size()>=data.capacity()) __builtin_unreachable();if constexpr(std::is_invocable_v<decltype(generator),int>){data.push_back(generator(i));}else{data.push_back(generator());}}for(int i=number;--i;) Detail::template combine<true>(data[i],data[i<<1],data[i<<1|1]);}private:static bool evaluatesToTrue(auto const& fn){if constexpr(std::is_same_v<decltype(fn()),void>){fn();return false;}else{return fn();}}
#define IS_TRUE(expr...) evaluatesToTrue([&]{return (expr);})
template<class F,class T>static decltype(auto) invokeWithOptionalLayer(F const& f,T&& t,int layer) {if constexpr(std::is_invocable_v<F,T&&>) return f(std::forward<T>(t));else return f(std::forward<T>(t),layer);}public:static void forStrictAncestorIndexDown(int node,auto const& fn){for(int shift=31^__builtin_clz(node);shift;--shift)if(IS_TRUE(fn(node>>shift))) break;}static void forStrictAncestorIndexUp(int node,auto const& fn){for(int y=node>>1;y;y>>=1)if(IS_TRUE(fn(y))) break;}static void forRangeIndex(int leftNode,int rightNode,auto const& leftfn,auto const& rightfn){int layer=0;while(leftNode<rightNode){if(leftNode&1) if(IS_TRUE(invokeWithOptionalLayer(leftfn,leftNode++,layer))) break;if(rightNode&1) if(IS_TRUE(invokeWithOptionalLayer(rightfn,--rightNode,layer))) break;leftNode>>=1;rightNode>>=1;++layer;}}
#undef IS_TRUE
int offset()const{return int(data.size()/2u);}void combineAll(int node){assert(node>=offset());forStrictAncestorIndexUp(node,[&](int it){Detail::template combine<false>(data[it],data[it<<1],data[it<<1|1]);});}void forRange(int leftNode,int rightNode,auto const& leftfn,auto const& rightfn){assert(leftNode>=offset());assert(rightNode>=offset());forRangeIndex(leftNode,rightNode,[&](auto it,auto layer){return invokeWithOptionalLayer(leftfn,data[it],layer);},[&](auto it,auto layer){return invokeWithOptionalLayer(rightfn,data[it],layer);});}void forRange(int leftNode,int rightNode,auto const& fn){forRange(leftNode,rightNode,fn,fn);}template<class T> T reduceRange(int leftNode,int rightNode,T initial,auto const& function) {forRange(leftNode,rightNode,[&](Node const& node){initial=function(std::move(initial),node);});return initial;}};

struct Node{ int count; int64_t sum; };
struct SegmentTree: SegmentTreeTemplate<Node, SegmentTree>{
	using SegmentTreeTemplate::SegmentTreeTemplate;
	
	static void push(Node&, Node&){ }
	template<bool first>
	static void combine(Node& parent, Node const& left, Node const& right){ 
		parent.count=left.count+right.count;
		parent.sum=left.sum+right.sum;
	}

	// other methods
	void set(int node, Node value){
		data[node]=value; combineAll(node);
	}
	void add(int index, int64_t value){
		int node=index+offset();
		set(node, {data[node].count+1, data[node].sum+value});
	}
	void remove(int index, int64_t value){
		int node=index+offset();
		assert(data[node].count); assert(data[node].sum>=value);
		set(node, {data[node].count-1, data[node].sum-value});
	}

	Node get(int left, int right){
		left+=offset(); right+=offset();
		return reduceRange(left, right, Node{}, [](Node result, Node node){
			Node next; combine<true>(next, result, node); return next;
		});
	}

	int extract(int node, int pos) const{
		assert(0<=pos and pos<=data[node].count);
		if(pos==data[node].count){pos=0;++node;}
		while(node<offset()){
			node<<=1;
			if(pos>=data[node].count){
				pos-=data[node++].count;
			}
		}
		return node;
	}

	int center(int left, int right){
		auto const count=get(left, right).count;
		if(count==0) return left;
		assert(count%2==0); assert(count!=0);
		int result=-1;
		int left_=count/2, right_=count/2;
		forRangeIndex(left+offset(), right+offset(),[&](int node){
			if(data[node].count>=left_){
				assert(result<0);
				result=extract(node, left_);
				return true;
			}
			left_-=data[node].count;
			return false;
		},[&](int node){
			if(data[node].count>=right_){
				assert(result<0);
				result=extract(node, data[node].count-right_);
				return true;
			}
			right_-=data[node].count;
			return false;
		});
		assert(result>=offset());
		if(result==offset()*2) result>>=1;
		result-=offset();

		assert(left<=result and result<=right);
		assert(get(left, result).count==count/2);
		assert(get(result, right).count==count/2);
		return result;
	}
};

struct Function{
	std::vector<int64_t> allValues;
	SegmentTree tree;

	void build(){
		std::sort(begin(allValues), end(allValues));
		allValues.erase(std::unique(begin(allValues), end(allValues)), end(allValues));

		assert(tree.data.empty());
		tree.assign((int)allValues.size());
	}

	int64_t factor{};
	
	void fakeAdd(std::pair<int, int> it){
		allValues.push_back(it.first);
		allValues.push_back(it.second);
	}

	void add(std::pair<int, int> it){
		factor+=it.second-it.first;
		assert(it.first<it.second);
		for(auto it: {it.first, it.second}){
			tree.add(int(std::lower_bound(begin(allValues), end(allValues), it)-begin(allValues)), it);
		}
	}
	void remove(std::pair<int, int> it){
		factor-=it.second-it.first;
		assert(factor>=0);
		assert(it.first<it.second);
		for(auto it: {it.first, it.second}){
			tree.remove(int(std::lower_bound(begin(allValues), end(allValues), it)-begin(allValues)), it);
		}
	}
	int64_t calculateTwice(int64_t twicePos) {
		auto info=tree.get(
				int(std::upper_bound(begin(allValues), end(allValues), twicePos/2)-allValues.begin()),
				tree.offset());
		auto [countAll, sumAll]=tree.data[1];
		assert(countAll%2==0);
		assert(info.count<=countAll);

		int64_t result=-sumAll+info.sum*2+twicePos*(countAll/2-info.count);
		assert(([&]{
			int64_t naive{};
			for(int index=0; index<tree.offset(); ++index){
				auto const c=tree.data[index+tree.offset()].count;
				assert(c>=0);
				naive+=c*(
						std::abs(allValues[index]*2-twicePos)
						);
			}
			assert(naive%2==0); naive/=2;
			assert(naive==result);
			return true;
		}()));
		return result-factor;
	}
	int64_t calculate(int64_t pos){return calculateTwice(pos*2);}
	int64_t minPos() {
		return allValues[tree.center(0, tree.offset())];
	}

};

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 center=[&](auto it){return it.first+it.second;};
	if(numBridge==2 and numPeople<=1000){
		std::sort(begin(terms), end(terms),[&](auto first, auto sec){
			return center(first)<center(sec);
		});
		auto result=INT64_MAX;

		Function sumFunction, diffFunction, added, addFlipped;

		for(auto t: terms){
			sumFunction.fakeAdd(t);
			added.fakeAdd(t);
			addFlipped.fakeAdd(t);

			diffFunction.fakeAdd(t);
			addFlipped.fakeAdd({-t.second, t.first});
		}
		sumFunction.build();
		diffFunction.build();
		added.build();
		addFlipped.build();
		for(auto t: terms){
			sumFunction.add(t);
			added.add(t);
			addFlipped.add(t);
		}


		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())
			
			if(index!=0){
				auto t=terms[index-1];

				diffFunction.add(t);
				addFlipped.add({-t.second, t.first});

				sumFunction.remove(t);
				addFlipped.remove(t);
			}

			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){
				auto const twiced=std::max((int64_t)twicedleft,
						std::min((int64_t)twicedright, (int64_t)added.minPos()*2));
				result=std::min(result, sumFunction.calculateTwice(twiced)+diffFunction.calculateTwice(twiced));
			}
			else if(twiced<twicedleft){
				auto const twicer=std::max<int64_t>(0, twicedleft+(int64_t)addFlipped.minPos()*2);
				result=std::min(result, sumFunction.calculateTwice(twicedleft+twicer)+
						diffFunction.calculateTwice(twicedleft-twicer));
			}
			else if(twiced>twicedright){
				auto const twicer=std::max<int64_t>(0, twicedright+(int64_t)addFlipped.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