#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){
ll p=*(--l1.end());
l1.erase(p);
r1.insert(p);
new_med=*(--l1.end());
dist1+=((sz1-1)/2+1)*(med-new_med)-(sz1/2-1)*(med-new_med);
}
if(r1.size()>sz1/2){
ll p=*(r1.begin());
r1.erase(p);
l1.insert(p);
new_med=p;
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) r2.erase(num);
else l2.erase(num);
dist2-=(abs(num-med));
if(l2.size()>(sz2+1)/2){
ll p=*(--l2.end());
l2.erase(p);
r2.insert(p);
new_med=*(--l2.end());
dist2+=((sz2+1)/2+1)*(med-new_med)-(sz2/2-1)*(med-new_med);
}
if(r2.size()>sz2/2){
ll p=*(r2.begin());
r2.erase(p);
l2.insert(p);
new_med=p;
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==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++){
l=*r2.begin();
l2.insert(l);
r2.erase(l);
}
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:39: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]
39 | if(l2.size()>(sz2+1)/2){
| ~~~~~~~~~^~~~~~~~~~
bridge.cpp:46: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]
46 | if(r2.size()>sz2/2){
| ~~~~~~~~~^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:73: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]
73 | 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 |
384 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 |
356 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 |
0 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 |
20 ms |
5176 KB |
Output is correct |
| 13 |
Correct |
43 ms |
5236 KB |
Output is correct |
| 14 |
Correct |
30 ms |
4672 KB |
Output is correct |
| 15 |
Correct |
23 ms |
3304 KB |
Output is correct |
| 16 |
Correct |
27 ms |
5136 KB |
Output is correct |
| 17 |
Correct |
32 ms |
5176 KB |
Output is correct |
| 18 |
Correct |
37 ms |
5228 KB |
Output is correct |
| 19 |
Correct |
40 ms |
5348 KB |
Output is correct |
| 20 |
Correct |
32 ms |
5200 KB |
Output is correct |
| 21 |
Correct |
37 ms |
5176 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
