Submission #736631

#	Time	Username	Problem	Language	Result	Execution time	Memory
736631		minhcool	Palembang Bridges (APIO15_bridge)	C++17	49 / 100	2074 ms	31048 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, k, a[N];
 
vector<pair<int, ii>> queries;
 
vector<int> diff;
 
int pref[N], suff[N];
 
ii IT1[N << 2], IT2[N << 2];
 
void upd1(int id, int l, int r, int pos, int val){
	if(l == r){
		IT1[id].fi++;
		IT1[id].se -= val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upd1(id << 1, l, mid, pos, val);
	else upd1(id << 1 | 1, mid + 1, r, pos, val);
	IT1[id].fi = IT1[id << 1].fi + IT1[id << 1 | 1].fi;
	IT1[id].se = IT1[id << 1].se + IT1[id << 1 | 1].se;
}
 
ii total = {0, 0};
 
void get1(int id, int l, int r, int L, int R){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		total.fi += IT1[id].fi;
		total.se += IT1[id].se;
		return;
	}
	int mid = (l + r) >> 1;
	get1(id << 1, l, mid, L, R);
	get1(id << 1 | 1, mid + 1, r, L, R);
}
 
void upd2(int id, int l, int r, int pos, int val){
	if(l == r){
		IT2[id].fi--;
		IT2[id].se += val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upd2(id << 1, l, mid, pos, val);
	else upd2(id << 1 | 1, mid + 1, r, pos, val);
	IT2[id].fi = IT2[id << 1].fi + IT2[id << 1 | 1].fi;
	IT2[id].se = IT2[id << 1].se + IT2[id << 1 | 1].se;
}
 
void get2(int id, int l, int r, int L, int R){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		total.fi += IT2[id].fi;
		total.se += IT2[id].se;
		return;
	}
	int mid = (l + r) >> 1;
	get2(id << 1, l, mid, L, R);
	get2(id << 1 | 1, mid + 1, r, L, R);
}
 
int cal(int x){
	total = {0, 0};
	int pos = lower_bound(diff.begin(), diff.end(), x) - diff.begin();
	get1(1, 1, diff.size() - 1, 1, pos);
	get2(1, 1, diff.size() - 1, pos, diff.size() - 1);
//	cout << "OK " << x << " " << total.fi << " " << total.se << "\n";
	return x * total.fi + total.se;
}
 
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
 
void process(){
	cin >> k >> n;
	int answer = 0;
	for(int i = 1; i <= n; i++){
		char a, b;
		int c, d;
		cin >> a >> c >> b >> d;
		if(a == b){
			answer += abs(c - d);
			continue;
		}
		queries.pb({c + d, {min(c, d), max(c, d)}});
		diff.pb(c), diff.pb(d);
	}
	diff.pb(-1);
	sort(queries.begin(), queries.end());
	sort(diff.begin(), diff.end());
	diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
	int cnt = 0;
	for(auto it : queries){
	//	cout << it.fi << " " << it.se.fi << " " << it.se.se << "\n";
		cnt++;
		pref[cnt] = oo;
		int posi1 = lower_bound(diff.begin(), diff.end(), it.se.fi) - diff.begin();
		int posi2 = lower_bound(diff.begin(), diff.end(), it.se.se) - diff.begin();
		upd1(1, 1, diff.size() - 1, posi2, it.se.se);
		upd2(1, 1, diff.size() - 1, posi1, it.se.fi);
		int le = 1, ri = diff.size() - 1;
		while(le < ri - 3){
			int mid1 = (le + ri) >> 1, mid2 = mid1 + 1;
			int x = cal(diff[mid1]), y = cal(diff[mid2]);
			pref[cnt] = min(pref[cnt], min(x, y));
			if(x > y) le = mid1;
			else ri = mid2;
		}
	//	cout << le << " " << ri << "\n";
		for(int i = le; i <= ri; i++) pref[cnt] = min(pref[cnt], cal(diff[i]));
		//cout << cnt << " " << pref[cnt] << "\n";
		//total = {0, 0};
	}
	for(int i = 1; i <= (diff.size() << 2); i++){
		IT1[i] = {0, 0}, IT2[i] = {0, 0};
	}
	reverse(queries.begin(), queries.end());
	cnt = queries.size();
	for(auto it : queries){
		cnt--;
		suff[cnt] = oo;
		int posi1 = lower_bound(diff.begin(), diff.end(), it.se.fi) - diff.begin();
		int posi2 = lower_bound(diff.begin(), diff.end(), it.se.se) - diff.begin();
		upd1(1, 1, diff.size() - 1, posi2, it.se.se);
		upd2(1, 1, diff.size() - 1, posi1, it.se.fi);
		int le = 1, ri = diff.size() - 1;
		while(le < ri - 3){
			int mid1 = (le + le + ri) / 3, mid2 = (le + ri + ri) / 3;
			int x = cal(diff[mid1]), y = cal(diff[mid2]);
			suff[cnt] = min(suff[cnt], min(x, y));
			if(x > y) le = mid1;
			else ri = mid2;
		}
		for(int i = le; i <= ri; i++) suff[cnt] = min(suff[cnt], cal(diff[i]));
		//cout << cnt << " " << suff[cnt] << "\n";
	}
	int ans = oo;
	for(int i = 0; i <= queries.size(); i++){
		if(i && i < queries.size() && k == 1) continue;
		ans = min(ans, pref[i] + suff[i]);
	//	cout << i << " " << pref[i] << " " << suff[i] << "\n";
	}
	ans *= 2;
	ans += answer;
	ans += queries.size();
	for(auto it : queries) ans += abs(it.se.fi - it.se.se);
	cout << ans;
	//cout << ans << " " << ans + answer << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
 
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'void process()':
bridge.cpp:138:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i = 1; i <= (diff.size() << 2); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:162:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |  for(int i = 0; i <= queries.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
bridge.cpp:163:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   if(i && i < queries.size() && k == 1) continue;
      |           ~~^~~~~~~~~~~~~~~~

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