Submission #261075

#	Time	Username	Problem	Language	Result	Execution time	Memory
261075		user202729	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	90 ms	4216 KiB

bridge

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

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';
	}
}

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