Submission #884862

#	Time	Username	Problem	Language	Result	Execution time	Memory
884862		Hakiers	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	4 ms	8940 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll oo = 2e18;
constexpr int MAXN = 2e5 + 7;
ll translate[MAXN];
vector<pair<ll, ll>> T[MAXN];
pair<ll, ll> input[MAXN];
priority_queue<pair<ll, pair<ll, ll>>> R;
priority_queue<ll> L;
ll LSUM, RSUM;
map<ll, int> mapa;
pair<ll, ll> SUMS[MAXN][2];
ll total;
int k, n, D;
 
void remove(ll l){
	while(L.size() && -(L.top()) <= translate[l]){
		LSUM += L.top();
		L.pop();
	}
}
 
void updateR(ll l, ll r){
 
	for(auto [a, b] : T[r]){
		R.push({a+b, {a, b}});
		RSUM += b;
	}
	
	while(R.size() && R.top().first >= translate[l] + translate[r]){
		L.push(-R.top().second.first);
		RSUM -= R.top().second.second;
		LSUM += R.top().second.first;
		R.pop();
	}
	remove(l);
}
 
ll check(ll l, ll r, bool change){
	ll res = 0;
	
	priority_queue<pair<ll, pair<ll, ll>>> Rcpy;
	priority_queue<ll> Lcpy;
	ll LSUMcpy;
	ll RSUMcpy;
	if(!change){
		Rcpy = R;
		Lcpy = L;
		LSUMcpy = LSUM;
		RSUMcpy = RSUM;
	}
	
	updateR(l, r);
	res += 2*(translate[l]*SUMS[l-1][0].second - SUMS[l-1][0].first);
	res += 2*(SUMS[r+1][1].first - translate[r]*SUMS[r+1][1].second);
	res += 2*(LSUM - ll(L.size())*translate[l]);
	res += 2*(ll(R.size())*translate[r] - RSUM);
	
	if(!change){
		R = Rcpy;
		L = Lcpy;
		LSUM = LSUMcpy;
		RSUM = RSUMcpy;
	}
	
	return res;
}
 
ll solve(){
	ll best = oo;
	int r = 0;
	
	for(int i = 1; i <= D; i++){
		while(r < D && (k > 1 || r < i) && (check(i, r+1, 0) <= best || r < i)){
			best = min(check(i, ++r, 1), best);
			//if(best == 0) cout << "l: " << i << " r: " << r << "\n";
		}
		remove(i);
	}
	
	return best;
}
 
void scale(){
	
	int act = 0;
	
	for(auto it = mapa.begin(); it != mapa.end(); ++it){
		it->second = ++act;
		translate[act] = it->second;
	}
	
	D = act;
	
	for(int i = 1; i <= n; i++){
		if(input[i].first == -1) continue;
		input[i].first = mapa[input[i].first];
		input[i].second = mapa[input[i].second];
	}
}
 
void compute(){
	
	for(int i = 1; i <= n; i++){
		if(input[i].first == -1) continue;
		SUMS[input[i].second][0].first += translate[input[i].second];
		SUMS[input[i].second][0].second++;
		
		SUMS[input[i].first][1].first += translate[input[i].first];
		SUMS[input[i].first][1].second++;
		
		T[input[i].second].push_back({translate[input[i].first], translate[input[i].second]});
	}
	
	for(int i = 1; i <= D; i++){
		SUMS[i][0].first += SUMS[i-1][0].first;
		SUMS[i][0].second += SUMS[i-1][0].second;
	}
	
	for(int i = D; i >= 1; i--){
		SUMS[i][1].first += SUMS[i+1][1].first;
		SUMS[i][1].second += SUMS[i+1][1].second;
	}
 
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n;
	
	for(int i = 1; i <= n; i++){
		char x, y;
		ll a, b;
		cin >>x >> a >> y >> b;
		if(b < a) swap(a, b);
		mapa[a];
		mapa[b];
		if(x != y){
			total += (b-a + 1);
			input[i] = {a, b};
		}
		else{
			total += (b-a);
			input[i] = {-1, -1};
		}
	}
	
	scale();
	compute();
	
	cout << total + solve() << "\n";
	
}
 
 
/*
 
 
 
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
 
*/

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