oj.uz

Submission #736630

# Submission time Handle Problem Language Result Execution time Memory
736630 2023-05-06T03:43:52 Z minhcool Palembang Bridges (APIO15_bridge) C++17
49 / 100
 2000 ms 7248 KB 
#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 + le + ri) / 3, mid2 = (le + ri + ri) / 3;
			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

bridge.cpp: In function 'void process()':
bridge.cpp:139: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]
  139 |  for(int i = 1; i <= (diff.size() << 2); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:164: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]
  164 |  for(int i = 0; i <= queries.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
bridge.cpp:165: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]
  165 |   if(i && i < queries.size() && k == 1) continue;
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 622 ms 712 KB Output is correct
5 Correct 574 ms 584 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 617 ms 824 KB Output is correct
8 Correct 631 ms 564 KB Output is correct
9 Correct 629 ms 644 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 644 ms 572 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 607 ms 656 KB Output is correct
5 Correct 565 ms 588 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 629 ms 728 KB Output is correct
8 Correct 629 ms 680 KB Output is correct
9 Correct 617 ms 652 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 631 ms 704 KB Output is correct
12 Correct 37 ms 6020 KB Output is correct
13 Execution timed out 2062 ms 5244 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 336 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 336 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 16 ms 448 KB Output is correct
15 Correct 599 ms 676 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 10 ms 340 KB Output is correct
18 Correct 76 ms 440 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 629 ms 868 KB Output is correct
21 Correct 621 ms 584 KB Output is correct
22 Correct 581 ms 680 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 612 ms 688 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 404 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 16 ms 428 KB Output is correct
15 Correct 593 ms 872 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 10 ms 336 KB Output is correct
18 Correct 77 ms 484 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 620 ms 752 KB Output is correct
21 Correct 607 ms 708 KB Output is correct
22 Correct 582 ms 596 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 628 ms 796 KB Output is correct
25 Correct 37 ms 6720 KB Output is correct
26 Correct 1569 ms 7248 KB Output is correct
27 Execution timed out 2048 ms 6816 KB Time limit exceeded
28 Halted 0 ms 0 KB -