Submission #302405

#	Time	Username	Problem	Language	Result	Execution time	Memory
302405		user202729	Palembang Bridges (APIO15_bridge)	C++17	78 / 100	1082 ms	17124 KiB

bridge

// might be fast enough. Still log^terrible.



#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); // okay
		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 pos)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), pos);
		//assert(iterator!=positions.end()); // all passed
		int64_t const value2=getAtIndex(int(iterator-positions.begin()));
		if(*iterator==pos) return value2;
		//assert(iterator!=positions.begin());
		//assert(iterator[-1]<pos); assert(pos<iterator[0]);
		int64_t const value1=getAtIndex(int(iterator-positions.begin())-1);

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

	// 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()); // okay
			return (*this).rawGet(pos)[0];
		};
		int pos=offset(); // relatively small (compared to INT_MAX)
		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));
		}

		/*
#warning
		[&]{ // (slow) ensure that the found index is really the minimum.
			for(int pos1=0; pos1<offset(); ++pos1){
				if(not(getAtIndex(pos1)>=result.first)) std::exit(1);
			}
			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;

	// 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.

	if(positions.size()<=2){
		std::cout<<result<<'\n';
		return 0;
	}

	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){
		//assert(first<=sec); // okay
		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); // okay
		//assert(positions[isec]==sec);
		//assert(tree.offset()==(int)positions.size()); // okay
		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() ? positions.back()*2: queries[slice][0]+queries[slice][1];
		// 2e9'ish
		if(curSum>lastSum){
			// find minAdd in the current slice (first<=sec, lastSum<=first+sec<=curSum)

			auto const searchFunction=[&](auto function, int left, int right){
				// minAdd=min(minAdd, function(i)) for i in left..=right
				// given that function is ternary (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; step>>=1){
					if((int64_t)pos-step>=left) process(pos-step);
					if((int64_t)pos+step<=right) process(pos+step);
				}
				minAdd=std::min(minAdd, value);

				//assert(value==function(pos)); // okay
				//assert(left<=pos); assert(pos<=right);
				/*
				assert(right-left<=500); // * only while debugging
				for(int i=left; i<=right; ++i)
					assert(function(i)>=value);
					*/
			};
			auto const searchSlope=[&](int sum){
				//assert(lastSum<=sum); assert(sum<=curSum); // okay
				//assert(sum>=0); // okay, implied by previous

				// 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(x>=0); // looks good
					//assert(first<=sec); // okay, basic arithmetic and implied by above
					//assert(first+sec==sum); // ^

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

			auto const searchC=[&]{
				searchFunction([&](int value){
					//assert(lastSum<=value+value); // okay
					//assert(value+value<=curSum);

					return ffirst.getAtValue(value)+fsec.getAtValue(value);
				}, std::max(positions[0], (lastSum+1)>>1), std::min(positions.back(), curSum>>1));
			};

			auto const ifirst=ffirst.minIndex();
			auto const isec=fsec.minIndex();
			auto const sum1=positions[ifirst]+positions[isec]; // range: 2e9'ish

			auto const minValue=ffirst.getAtIndex(ifirst)+fsec.getAtIndex(isec);
			if(minValue<minAdd){
				if(lastSum<=sum1 and sum1<=curSum and ifirst<=isec){
					minAdd=std::min(minAdd, minValue);
				}else{ // minValue is not reachable. Only larger values are.
					searchC();
					if(sum1<lastSum)
						searchSlope(lastSum);
					if(curSum<sum1)
						searchSlope(curSum);
				}
			}

			lastSum=curSum;
		}else{
			//assert(curSum==lastSum); // okay
		}

		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: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37