#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int, int>;
struct GetMedian{
multiset<ll> fi;
multiset<ll> se;
ll fsum, ssum;
void add(ll x){
se.insert(x);
ssum+=x;
while(fi.size() > se.size()){
ll val=*fi.rbegin();
fsum-=val;
fi.erase(fi.find(val));
ssum+=val;
se.insert(val);
}
while(se.size() > fi.size()){
ll val=*se.begin();
ssum-=val;
se.erase(se.begin());
fsum+=val;
fi.insert(val);
}
}
ll get(){
ll med=*se.begin();
return (med * fi.size() - fsum) + (ssum - med * se.size());
}
void clear(){
fi.clear();
se.clear();
fsum=ssum=0;
}
};
int k, n;
const int N=1e5+13;
int a[N];
ll res;
char c1, c2;
int x, y;
namespace sub1{
vector<int> v;
void solve(){
for(int i=1; i<=n; i++){
cin >> c1 >> x >> c2 >> y;
if(c1==c2){
res+=abs(x-y);
}
else{
v.push_back(x);
v.push_back(y);
++res;
}
}
sort(begin(v), end(v));
for(int c: v){
res+=abs(c-v[v.size()/2]);
}
cout << res;
}
}
vector<pair<int, int>> v;
ll l[N];
ll r[N];
void solve(){
cin >> k >> n;
if(k==1){
sub1::solve();
exit(0);
}
for(int i=1; i<=n; i++){
cin >> c1 >> x >> c2 >> y;
if(c1==c2){
res+=abs(x-y);
}
else{
if(x > y) swap(x, y);
v.push_back(make_pair(x, y));
++res;
}
}
if(v.empty()){
cout << res;
return;
}
sort(begin(v), end(v), [&](pii x, pii y){
return x.fi + x.se < y.fi + y.se;
});
GetMedian sus;
for(int i=1; i<=n; i++){
sus.add(v[i].fi);
sus.add(v[i].se);
l[i]=sus.get();
}
sus.clear();
for(int i=n; i>=1; i--){
sus.add(v[i].fi);
sus.add(v[i].se);
r[i]=sus.get();
}
ll ans=l[n];
for(int i=1; i<n; i++){
ans=min(ans, l[i]+r[i+1]);
}
cout << res+ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
14 ms |
1500 KB |
Output is correct |
13 |
Correct |
28 ms |
1500 KB |
Output is correct |
14 |
Correct |
28 ms |
1500 KB |
Output is correct |
15 |
Correct |
16 ms |
992 KB |
Output is correct |
16 |
Correct |
16 ms |
1500 KB |
Output is correct |
17 |
Correct |
19 ms |
1496 KB |
Output is correct |
18 |
Correct |
23 ms |
1500 KB |
Output is correct |
19 |
Correct |
28 ms |
1500 KB |
Output is correct |
20 |
Correct |
25 ms |
1500 KB |
Output is correct |
21 |
Correct |
25 ms |
1496 KB |
Output is correct |
# |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |