Submission #301982

#	Time	Username	Problem	Language	Result	Execution time	Memory
301982		user202729	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	512 KiB

bridge

// ... ...

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

std::vector<int> positions; // it's more convenient to make it global. It's not changed very frequently anyway

/*
 * stores a convex piecewise linear function.
 * the cuts must be in positions.
 */

struct Tree{
	using Data=std::array<int64_t, 2>; // sort of parallel data tuple. Can be used for anything.
	std::vector<Data> data; // "lazy"
	Tree(std::size_t number): data(number*2){}

	static void add1(Data& first, Data sec){
		first[0]+=sec[0];
		first[1]+=sec[1];
	}

	int offset() const{return int(data.size()/2);}

	// get raw {a, b} value at a particular position.
	Data rawGet(int index)const{
		index+=offset();
		Data result{};
		for(; index; index>>=1)
			add1(result, data[index]);
		return result;
	}

	// add a value to a range.
	void add(int left, int right, Data const value){
		left+=offset(); right+=offset();
		assert(left<=right);
		while(left<right){
			if(left&1) add1(data[left++], value);
			if(right&1) add1(data[--right], value);
			left>>=1; right>>=1;
		}
	}

	// self explanatory.
	int64_t getAtIndex(int index)const{
		auto const [a, b]=(*this).rawGet(index);
		return (int64_t)a*positions[index]+b;
	}

	// get the function value, at a particular (possibly not in positions) position.
	int64_t getAtValue(int value)const{


		// interpolate if necessary. (always work in this particular problem...)
		// could be a little simpler (by explicitly store the slope on each segment), but...
		// :(

		auto const iterator=std::lower_bound(begin(positions), end(positions), value);
		int64_t const value2=getAtIndex(int(iterator-positions.begin()));
		if(*iterator==value) return value2;
		int64_t const value1=getAtIndex(int(iterator-positions.begin())-1);

		auto const number=value1*(*iterator-value)+value2*(value-iterator[-1]);
		auto const de=*iterator-iterator[-1];
		assert(number%de==0);
		return number/de;
	}

	// get any index for which getAtIndex returns the minimum value.
	int minIndex() const{

		// assumes some specific kind of function shape.
		// currently O(log^2 n)
		// could be O(log n) instead.
		// :(

		// the boundary binary search might be reducible to O(log n)
		// too with some careful planning. I don't know.

		auto const value=[&](int pos){
			assert(0<=pos and pos<offset());
			return (*this).rawGet(pos)[0];
		};
		int pos=offset();
		for(int step=1<<30; step>>=1;){
			if(pos-step>=0 and value(pos-step)>=0) pos-=step;
		}
		// now pos=first element with value >=0

		std::pair<int64_t, int> result{INT64_MAX, INT_MAX};
		for(int pos1=pos-1; pos1<=pos; ++pos1){ // perhaps this can be simpler? I don't know...
			if((unsigned) pos1<(unsigned)offset())
				result=std::min(result, std::make_pair(getAtIndex(pos1), pos1));
		}

		assert(([&]{ // (slow) ensure that the found index is really the minimum.
			for(int pos1=0; pos1<offset(); ++pos1){
				assert(getAtIndex(pos1)>=result.first);
			}
			return true;
		}()));
		return result.second;
	}
};

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int k, number; std::cin>>k>>number;
	if(k==1) return 1;
	int64_t result{};
	std::vector<std::array<int, 2>> queries;
	// read into queries, and prepare result (nonoptimizable part).
	// this part should not be wrong.
	for(int _=0; _<number; ++_){
		char a, b; int first, sec;
		std::cin>>a>>first>>b>>sec;
		if(first>sec) std::swap(first, sec);
		result+=sec-first; // minimum required
		if(a!=b){
			result+=1; // need to cross a bridge anyway
			queries.push_back({first, sec});
			positions.push_back(first); positions.push_back(sec);
		}
	}
	number=-1;

	if(queries.empty()){
		std::cout<<result<<'\n';
		return 0;
	}

	// sort positions.
	std::sort(begin(positions), end(positions));
	positions.erase(std::unique(begin(positions), end(positions)), end(positions));
	// from now on, positions are not changed anymore.
	auto minAdd=INT64_MAX;
	// minimum of the function (it's hard to explain.)

	std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
		return first[0]+first[1]<sec[0]+sec[1];
	});

	Tree ffirst(positions.size()), fsec(positions.size());
	// in this problem value (a, b) means y=a*x+b

	/*
	first and sec are values in positions.
	Add the function multiplier*max(first-x, 0, x-sec) to tree.
	(it's convex if multiplier>=0.)
	*/
	auto const addSlope=[&](Tree& tree, int first, int sec, int multiplier){
		auto const ifirst=int(std::lower_bound(begin(positions), end(positions), first)-begin(positions));
		auto const isec=int(std::lower_bound(begin(positions), end(positions), sec)-begin(positions));
		assert(positions[ifirst]==first);
		assert(positions[isec]==sec);
		assert(first<=sec);
		assert(tree.offset()==(int)positions.size());
		tree.add(0, ifirst, {-1*multiplier, first*multiplier});
		tree.add(isec, tree.offset(), {1*multiplier, -sec*multiplier});
		// * Data could be std::pair<int, int64_t> * save implementation time!
	};
	for(auto [first, sec]: queries)
		addSlope(fsec, first, sec, 1);

	for(int slice=0, lastSum=0; slice<=(int)queries.size(); ++slice){
		int curSum=slice==(int)queries.size() ? INT_MAX: queries[slice][0]+queries[slice][1];
		if(curSum>lastSum){
			// find minAdd in the current slice (first<=sec, lastSum<=first+sec<=curSum)

			auto const ifirst=ffirst.minIndex();
			auto const isec=fsec.minIndex();
			auto const sum1=positions[ifirst]+positions[isec];
			auto const A=sum1<lastSum, B=sum1>curSum, C=ifirst>isec;

			auto const searchFunction=[&](auto function, int left, int right){
				// minAdd=min(minAdd, function(i)) for i in left..=right
				// given that function is tern any (or something like that) on the segment
				//
				// complexity: log(value) calls to function. (which is actually pretty terrible?)

				if(left>right) return; // just to be sure

				int pos=left; auto value=function(pos);
				auto const process=[&](int pos1){
					auto const value1=function(pos1);
					if(value1<value){
						pos=pos1; value=value1;
					}
				};
				for(int step=1<<30; step>>=1;){
					if(pos-step>=left) process(pos-step);
					if(pos+step<=right) process(pos+step);
				}
				minAdd=std::min(minAdd, value);
			};
			auto const searchSlope=[&](int sum){
				assert(sum>=0);
				assert(lastSum<=sum); assert(sum<=curSum);

				// diff -> (sum-diff)/2, (sum+diff)/2
				// diff=sum&1+2*x
				// => ((sum-sum&1-2x)/2, (sum+sum&1+2x)/2)
				// => (  (sum>>1)-x,  ((sum+1)>>1)+x  )
				// obviously first<=sec
				// need positions[0]<=first, sec<=positions.back()

				// (to clarify: it's not "necessary", the result remains correct without that,
				// but the current implementation of Tree::getAtValue can only handle those values)
				searchFunction([&](int x){
					auto const first=(sum>>1)-x, sec=((sum+1)>>1)+x;
					assert(first<=sec);
					assert(first+sec==sum);

					return ffirst.getAtValue(first)+fsec.getAtValue(sec);
				}, 0, std::min(positions.back()-((sum+1)>>1), (sum>>1)-positions[0]));
			};

			if(A){
				assert(not B);
				if(C){
					// some special case handler can be added here to be a little faster, but just in this case
					// it's okay to leave it empty
				}
				searchSlope(lastSum);

				// also the intersection with the (x==positions[0]) line
				// (yes, the restriction [positions[0], positions.back()] hurts.)
				int const first=positions[0];
				int const left=std::max(positions[0], lastSum-first),
					right=std::min(positions.back(), curSum-first);
				if(left<=right){
					int const sec=std::min(right, std::max(left, positions[isec]));
					assert(first<=sec); assert(first+sec<=curSum); assert(lastSum<=first+sec);
					minAdd=std::min(minAdd, ffirst.getAtValue(first)+fsec.getAtValue(sec));
				}
			}else if(B){
				if(C){
					// some special case handler can be added here to be a little faster, but just in this case
					// it's okay to leave it empty
				}
				searchSlope(curSum);

				// same as above
				int const sec=positions.back();
				int const left=std::max(positions[0], lastSum-sec),
					right=std::min(positions.back(), curSum-sec);
				if(left<=right){
					int const first=std::min(right, std::max(left, positions[ifirst]));
					assert(first<=sec); assert(first+sec<=curSum); assert(lastSum<=first+sec);
					minAdd=std::min(minAdd, ffirst.getAtValue(first)+fsec.getAtValue(sec));
				}
			}else if(C){
				// not sure if this case is necessary. (because having two coinciding bridges is not better)
				searchFunction([&](int value){
					assert(lastSum<=value+value);
					assert(value+value<=curSum);

					return ffirst.getAtValue(value)+fsec.getAtValue(value);
				}, std::max(positions[0], (lastSum+1)>>1), std::min(positions.back(), curSum>>1));
			}else{
				minAdd=std::min(minAdd, ffirst.getAtIndex(ifirst)+fsec.getAtIndex(isec));
			}

			lastSum=curSum;
		}else assert(curSum==lastSum);

		if(slice!=(int)queries.size()){
			// apply change from queries[slice]
			auto const [first, sec]=queries[slice];
			addSlope(fsec, first, sec, -1);
			addSlope(ffirst, first, sec, 1);
		}
	}

	std::cout<<result+minAdd*2<<'\n';
}

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