Submission #301751

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

bridge

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

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int k, number; std::cin>>k>>number;
	if(k==1 or number>1000) return 1;
	int64_t result{};
	std::vector<std::array<int, 2>> queries;
	std::vector<int> positions;
	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;
	}

	std::sort(begin(positions), end(positions));
	positions.erase(std::unique(begin(positions), end(positions)), end(positions));
	auto minAdd=INT64_MAX;
	for(auto y: positions){
		std::vector<std::pair<int, int>> changes; // increases in slope. (pos, delta).
		int64_t zeroValue{}; // value at zero.
		// slope at zero is always 0.
		// example: for function max(x, 0), changes={ {0, 1} }, zeroValue=0.

		for(auto [l, r]: queries){
			assert(l<=r);
			if(y<l){
				zeroValue+=l-y;
			}else if(y>r){
				auto const delta=std::min(l, y-r);
				zeroValue+=delta;
				changes.push_back({l-delta, -1});
				changes.push_back({l, 1});
				changes.push_back({r, 1});
			}
		}
		changes.push_back({y, 0}); // for convenience
		std::sort(begin(changes), end(changes), [&](auto const& first, auto const& sec){
			return first.first<sec.first;
		});

		int64_t value=zeroValue; int last=0, slope=0;
		for(auto [pos, delta]: changes){
			assert(pos>=last);
			assert(pos<=y);
			value+=slope*(pos-last);
			minAdd=std::min(minAdd, value);
			last=pos;
			if(pos==y) break;

			slope+=delta;
		}
		assert(last==y);
	}
	std::cout<<result+minAdd<<'\n';
}

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