#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
ll n,m,l,r,i,j,ii,jj,k,x,y,T,s,e,a[100005],b[100005],dist1,dist2,ans,sz1,sz2;
char ch1,ch2;
vector< pair<ll,ll> > v;
vector<ll> sub;
multiset<ll> l1,l2,r1,r2;
multiset<ll>::iterator it;
void nem(ll num){
ll med=*(--l1.end()),new_med;
if(num>med) r1.insert(num);
else l1.insert(num);
if(l1.size()>(sz1+1)/2){
it=(--l1.end());
l1.erase(it);
r1.insert(*it);
new_med=*(--l1.end());
dist1+=((sz1-1)/2+1)*(med-new_med)-(sz1/2-1)*(med-new_med);
}
if(r1.size()>sz1/2){
it=(r1.begin());
r1.erase(it);
l1.insert(*it);
new_med=*it;
dist1+=(sz1/2)*(new_med-med)-((sz1-1)/2)*(new_med-med);
}
dist1+=abs(num-new_med);
}
void has(ll num){
ll med=*(--l2.end()),new_med;
if(num>med){
it=r2.find(num);
r2.erase(it);
}
else{
it=l2.find(num);
l2.erase(it);
}
dist2-=(abs(num-med));
if(l2.size()>(sz2+1)/2){
it=(--l2.end());
l2.erase(it);
r2.insert(*it);
new_med=*(--l2.end());
dist2+=((sz2+1)/2+1)*(med-new_med)-(sz2/2-1)*(med-new_med);
}
if(r2.size()>sz2/2){
it=(r2.begin());
r2.erase(it);
l2.insert(*it);
new_med=*it;
dist2+=((sz2+2)/2)*(new_med-med)-((sz2+1)/2)*(new_med-med);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>T>>n;
for(i=1;i<=n;i++){
cin>>ch1>>l>>ch2>>r;
if(ch1==ch2) k+=abs(l-r);
else{
k++;
v.pb({l+r,i});
sub.pb(l);
sub.pb(r);
}
a[i]=l;
b[i]=r;
}
if(T==1){
sort(sub.begin(),sub.end());
for(i=0;i<sub.size();i++) k+=abs(sub[i]-sub[sub.size()/2]);
cout<<k;
return 0;
}
sort(v.begin(),v.end());
n=v.size();
if(n==0){
cout<<k;
return 0;
}
if(n==1){
cout<<k+abs(a[v[0].ss]-b[v[0].ss]);
return 0;
}
l1.insert(min(a[v[0].ss],b[v[0].ss]));
r1.insert(max(a[v[0].ss],b[v[0].ss]));
dist1=abs(a[v[0].ss]-b[v[0].ss]);
for(i=1;i<n;i++){
r2.insert(a[v[i].ss]);
r2.insert(b[v[i].ss]);
}
for(i=1;i<n;i++){
it=r2.begin();
l2.insert(*it);
r2.erase(it);
}
it=l2.end();
it--;
x=*it;
for(i=1;i<n;i++) dist2+=abs(a[v[i].ss]-x)+abs(b[v[i].ss]-x);
ans=dist2+dist1;
sz1=2;
sz2=2*(n-1);
for(i=1;i<n-1;i++){
sz1++;
nem(a[v[i].ss]);
sz1++;
nem(b[v[i].ss]);
sz2--;
has(a[v[i].ss]);
sz2--;
has(b[v[i].ss]);
ans=min(ans,dist1+dist2);
}
cout<<ans+k;
}
Compilation message
bridge.cpp: In function 'void nem(long long int)':
bridge.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
18 | if(l1.size()>(sz1+1)/2){
| ~~~~~~~~~^~~~~~~~~~
bridge.cpp:25:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
25 | if(r1.size()>sz1/2){
| ~~~~~~~~~^~~~~~
bridge.cpp: In function 'void has(long long int)':
bridge.cpp:45:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
45 | if(l2.size()>(sz2+1)/2){
| ~~~~~~~~~^~~~~~~~~~
bridge.cpp:52:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
52 | if(r2.size()>sz2/2){
| ~~~~~~~~~^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:79:18: 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]
79 | for(i=0;i<sub.size();i++) k+=abs(sub[i]-sub[sub.size()/2]);
| ~^~~~~~~~~~~
bridge.cpp: In function 'void nem(long long int)':
bridge.cpp:32:15: warning: 'new_med' may be used uninitialized in this function [-Wmaybe-uninitialized]
32 | dist1+=abs(num-new_med);
| ~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
25 ms |
5176 KB |
Output is correct |
13 |
Correct |
40 ms |
5168 KB |
Output is correct |
14 |
Correct |
30 ms |
4684 KB |
Output is correct |
15 |
Correct |
23 ms |
3264 KB |
Output is correct |
16 |
Correct |
31 ms |
5156 KB |
Output is correct |
17 |
Correct |
34 ms |
5136 KB |
Output is correct |
18 |
Correct |
35 ms |
5176 KB |
Output is correct |
19 |
Correct |
41 ms |
5264 KB |
Output is correct |
20 |
Correct |
29 ms |
5140 KB |
Output is correct |
21 |
Correct |
37 ms |
5252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |