oj.uz

Submission #882688

# Submission time Handle Problem Language Result Execution time Memory
882688 2023-12-03T13:06:55 Z Kel_Mahmut Palembang Bridges (APIO15_bridge) C++14
31 / 100
 181 ms 9776 KB 
#include<bits/stdc++.h>
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
#define pb push_back
typedef long long ll;
const int maxn = 1e5 + 5;
using namespace std;

int n, k;
vector<pair<ll, ll>> v;
vector<ll> u;
multiset<pair<ll, ll>> nxt, in;
multiset<pair<ll, pair<ll, ll>>> vis; // vis r'ye gore artan come l'ye gore artan
ll lft, rgt, lst;
ll ans = LONG_LONG_MAX, cur, rem;
bool ok;

ll dst(pair<ll, ll> p, ll ind){
	if(p.first <= ind && ind <= p.second) return 0;
	return 2*min(abs(p.first - ind), abs(p.second - ind));
}

int main(){
	cin >> k >> n;
	for(int i = 0; i < n; i++){
		char c1, c2;
		int a, b;
		cin >> c1 >> a >> c2 >> b;
		if(b > a) swap(a, b);
		rem+=a-b;
		if(c1!=c2){
			ok = 1;
			++rem;
			v.pb({b, a});
			u.pb(a), u.pb(b);
		}
	}
	rgt = n = v.size();
	sort(all(u));
	sort(all(v));
	if(!ok){
		cout << rem << endl;
		exit(0);
	}
	
	if(k == 2){
	for(int l = 0; l < 2*n; l++){
		cur = 0;
		lft = rgt = 0, lst = u[l];
		for(int i = 0; i < n; i++){
			cur += dst(v[i], u[l]);
			if(u[l] < v[i].first){
				nxt.insert(v[i]);
				rgt++;
			}
		}

		for(int r = l; r < 2*n; r++){
			cur += lft*2*(u[r] - lst) - rgt*2*(u[r] - lst);

			while(!nxt.empty() && (*nxt.begin()).first == u[r]){
				pair<ll, ll> p = *nxt.begin();
				in.insert({p.second, p.first});
				nxt.erase(nxt.begin());
				rgt--;
			}

			while(!in.empty() && (*in.begin()).first == u[r]){
				pair<ll, ll> p = *in.begin();
				in.erase(in.begin());
				pair<ll, ll> fix = {p.second, p.first};
				vis.insert({dst(fix, u[l]) - dst(fix, u[r]), fix});
				lft++;
			}
			while(!vis.empty() && dst((*vis.begin()).second, u[r]) > dst((*vis.begin()).second, u[l]) ){
				pair<ll, ll> p = (*vis.begin()).second;
				lft--;
				vis.erase(vis.begin());
				cur += dst(p, u[l]) - dst(p, u[r]);
			}
			ans = min(ans, cur);
			lst = u[r];
		}
		vis.clear();
		nxt.clear();
		in.clear();	
	}
	assert(ans!=LONG_LONG_MAX);
	cout << ans + rem << endl;
	} else{
		cur = rem;
		rgt = n, lst = lft = 0;
		multiset<pair<ll, ll>> come;
		multiset<ll> vs;
		for(int i = 0; i < n; i++){
			come.insert(v[i]);
			cur+=2*v[i].first;
		}
		ans = cur;
		for(int i = 0; i < 2*n; i++){
			cur += lft*2*(u[i] - lst) - rgt*2*(u[i] - lst);
			while(!come.empty() && (*come.begin()).first == u[i]){
				pair<ll, ll> p = *come.begin();
				vs.insert({p.second});
				come.erase(come.find(p));
				rgt--;
			} 
			while(!vs.empty() && *vs.begin() == u[i]){
				lft++;
				vs.erase(vs.begin());
			}
			ans = min(ans, cur);
			lst = u[i];
		}
		cout << ans << endl;
	}
	

	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 2 ms 448 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 65 ms 9652 KB Output is correct
13 Correct 127 ms 9688 KB Output is correct
14 Correct 98 ms 8628 KB Output is correct
15 Correct 81 ms 5968 KB Output is correct
16 Correct 85 ms 9776 KB Output is correct
17 Correct 93 ms 9648 KB Output is correct
18 Correct 104 ms 9664 KB Output is correct
19 Correct 109 ms 9656 KB Output is correct
20 Correct 94 ms 9652 KB Output is correct
21 Correct 100 ms 9776 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 452 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Incorrect 181 ms 516 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Incorrect 180 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -