oj.uz

Submission #402113

# Submission time Handle Problem Language Result Execution time Memory
402113 2021-05-11T10:35:31 Z amunduzbaev Palembang Bridges (APIO15_bridge) C++14
100 / 100
 320 ms 16736 KB 
/* made by amunduzbaev */
 
#include <bits/stdc++.h>
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
#define ff first
#define vv vector
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define tut(x) array<int, x> 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
 
template<class T> bool umin(T& a, const T& b) { return a > b? a = b, true:false; }
template<class T> bool umax(T& a, const T& b) { return a < b? a = b, true:false; }
//void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	//freopen((s+".out").c_str(),"w",stdout); }
//template<class T> tree<T, 
//less<T>, null_type, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, ans, q, res, a[N];
int pref[N], suf[N];
/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

void solve(int t_case){
	cin>>k>>n;
	vpii tt;
	vii pp;
	for(int i=0;i<n;i++){
		char a, b; int l, r; cin>>a>>l>>b>>r;
		if(a == b) res += abs(r - l);
		else tt.pb({min(l, r), max(l, r)});
	}
	ans = 0;
	vpii tt2;
	for(int i=0;i<sz(tt);i++) tt2.pb({tt[i].ff + tt[i].ss, i});
	sort(all(tt2));
	multiset<int> lx, rx;
	int rs = 0, ls = 0;
	for(int i=0;i<sz(tt2);i++){
		int in = tt2[i].ss;
		rx.insert(tt[in].ff), rx.insert(tt[in].ss);
		rs += tt[in].ff + tt[in].ss;
		lx.insert(*rx.begin()), ls += *rx.begin(), rs -= *rx.begin(), rx.erase(rx.begin());

		pref[i] = rs - ls;
	} lx.clear(), rx.clear(), ls = rs = 0;
	for(int i=sz(tt2)-1;i>=0;i--){
		int in = tt2[i].ss;
		lx.insert(tt[in].ff), lx.insert(tt[in].ss);
		ls += tt[in].ff + tt[in].ss;
		rx.insert(*--lx.end()), rs += *--lx.end(), ls -= *--lx.end(), lx.erase(--lx.end());

		suf[i] = rs - ls;
	} ans = suf[0];

	if(k == 2)
	for(int i=0;i+1<sz(tt2);i++) umin(ans, pref[i] + suf[i+1]);
	//cout<<ans<<" "<<res<<e" "<<sz(tt)<<"\n";
	cout<<ans + res + sz(tt)<<"\n";
}

signed main(){ 
	NeedForSpeed
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 170 ms 15132 KB Output is correct
13 Correct 320 ms 16676 KB Output is correct
14 Correct 276 ms 14096 KB Output is correct
15 Correct 133 ms 9952 KB Output is correct
16 Correct 167 ms 15992 KB Output is correct
17 Correct 169 ms 16640 KB Output is correct
18 Correct 168 ms 16372 KB Output is correct
19 Correct 187 ms 16736 KB Output is correct
20 Correct 168 ms 16308 KB Output is correct
21 Correct 180 ms 16464 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 372 KB Output is correct
24 Correct 2 ms 484 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 175 ms 15292 KB Output is correct
26 Correct 268 ms 15352 KB Output is correct
27 Correct 308 ms 16172 KB Output is correct
28 Correct 315 ms 16696 KB Output is correct
29 Correct 311 ms 16692 KB Output is correct
30 Correct 146 ms 8984 KB Output is correct
31 Correct 169 ms 16048 KB Output is correct
32 Correct 168 ms 16732 KB Output is correct
33 Correct 164 ms 16312 KB Output is correct
34 Correct 182 ms 16720 KB Output is correct
35 Correct 170 ms 16296 KB Output is correct
36 Correct 175 ms 16468 KB Output is correct
37 Correct 163 ms 15160 KB Output is correct