#include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef long long ll; struct pt{ ll x,y; bool operator<(const pt& r)const{ return x+y<r.x+r.y; } }; int K,N,sz; ll base,ans,sum; ll L[100010],R[100010]; pt a[100010]; priority_queue<ll> lo; priority_queue<ll,vector<ll>,greater<ll> > hi; void push(int x){ if(!hi.empty()&&x>=hi.top())hi.push(x); else lo.push(x); ll t; while(hi.size()+1<lo.size()){ t=lo.top();lo.pop(); hi.push(t); } while(hi.size()>lo.size()+1){ t=hi.top();hi.pop(); lo.push(t); } } void f(ll s[]){ for(int i=0;i<sz;i++){ push(a[i].x); push(a[i].y); //printf("%lld %lld\n",lo.top(),hi.top()); int mid=(lo.top()+hi.top())/2; for(int j=0;j<=i;j++){ s[i]+=abs(a[j].x-mid); s[i]+=abs(a[j].y-mid); } } } int main(){ //freopen("bridge.in","r",stdin); scanf("%d%d ",&K,&N); char tx,ty; ll x,y; for(int i=0;i<N;i++){ char tx[4], ty[4]; scanf("%s %lld %s %lld ",tx,&x,ty,&y); if(*tx==*ty){ base+=y-x-1; }else{ a[sz++]=pt{x,y}; } } base+=N; sort(a,a+sz); f(L); if(K==1){ printf("%lld",L[sz-1]+base); return 0; } reverse(a,a+sz); f(R); ans=1e18; for(int i=0;i<sz-1;i++){ ans=min(ans,L[i]+R[sz-2-i]); } printf("%lld",ans+base); }

bridge.cpp: In function 'int main()':
bridge.cpp:53:10: warning: unused variable 'tx' [-Wunused-variable]
     char tx,ty;
          ^
bridge.cpp:53:13: warning: unused variable 'ty' [-Wunused-variable]
     char tx,ty;
             ^
bridge.cpp:52:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d ",&K,&N);
                         ^
bridge.cpp:57:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %lld %s %lld ",tx,&x,ty,&y);
                                              ^