#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e9 + 69;
int k, n, home[maxn];
ll fa[maxn], fb[maxn], ans = 0;
vector<int> a, b, point;
ll calc(int i) {
int id = upper_bound(all(a), i) - a.begin();
ll res = 1LL * i * id - fa[id] + fa[(int) a.size()] - fa[id] - 1LL * i * ((int) a.size() - id);
id = upper_bound(all(b), i) - b.begin();
res = res + 1LL * i * id - fb[id] + fb[(int) b.size()] - fb[id] - 1LL * i * ((int) b.size() - id);
return res;
}
void sub1() {
for(auto i:a) point.pb(i);
for(auto i:b) point.pb(i);
sort(all(point));
fa[0] = fb[0] = 0;
for(int i = 1; i <= (int) a.size(); i++) fa[i] = fa[i - 1] + a[i - 1];
for(int i = 1; i <= (int) b.size(); i++) fb[i] = fb[i - 1] + b[i - 1];
sort(all(a));
sort(all(b));
ll mn = oo;
for(auto i:point) mini(mn, calc(i));
ans += (int) a.size() + mn;
}
struct sliding_median {
multiset<int> low, high;
ll lsum, rsum;
void init() {
multiset<int> tmp;
low = tmp;
high = tmp;
lsum = rsum = 0;
}
void fix() {
if(low.size() < high.size()) {
int val = *high.begin();
lsum += val;
rsum -= val;
low.insert(val);
high.erase(high.find(val));
} else if((int) low.size() > (int) high.size() + 1) {
int val = *low.rbegin();
lsum -= val;
rsum += val;
low.erase(low.find(val));
high.insert(val);
}
}
void update(int x) {
int med = (low.empty() ? oo:*low.rbegin());
if(x < med){
lsum += x;
low.insert(x);
}
else {
rsum += x;
high.insert(x);
}
fix();
}
void Remove(int x) {
if(low.find(x) != low.end()) {
lsum -= x;
low.erase(low.find(x));
}
else {
rsum -= x;
high.erase(high.find(x));
}
fix();
}
} s;
bool cmp(pa a, pa b) {
return a.fi + a.se < b.fi + b.se;
}
void sub2(){
int m = (int) a.size();
vector<pa> val;
for(int i = 0; i < m; i++) {
val.pb({a[i], b[i]});
}
sort(all(val), cmp);
s.init();
for(int i = 1; i <= m; i++) {
s.update(val[i - 1].fi);
s.update(val[i - 1].se);
fa[i] = s.rsum - s.lsum;
}
s.init();
ll mn = oo, sum = 0;
for(int i = m; i >= 1; i--) {
s.update(val[i - 1].fi);
s.update(val[i - 1].se);
mini(mn, fa[i - 1] + s.rsum - s.lsum);
}
ans += mn + m;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>k>>n;
ans = 0;
for(int i = 0; i < n; i++){
char ch1, ch2;
int x, y;
cin>>ch1>>x>>ch2>>y;
if(ch1 == ch2) ans += abs(x - y);
else {
home[i] = (ch1 == 'B');
if(ch1 == 'A') a.pb(x);
else b.pb(x);
if(ch2 == 'A') a.pb(y);
else b.pb(y);
}
}
if(k == 1) {
sub1();
} else {
sub2();
}
cout<<ans;
return 0;
}
Compilation message
bridge.cpp: In function 'void sub2()':
bridge.cpp:120:17: warning: unused variable 'sum' [-Wunused-variable]
120 | ll mn = oo, sum = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
