#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
const ll mod=998244353,mxn=2e5+5,lg=30,inf=1e18,minf=-1e9,Mxn=100000;
struct solve{
priority_queue<int>l;
priority_queue<int,vector<int>,greater<int>>r;
int suml=0,sumr=0,med=inf;
void add(int val){
med=getmed();
if(val>med)r.push(val),sumr+=val;
else l.push(val),suml+=val;
balance();
}
void balance(){
while(r.size()>l.size()+1){
l.push(r.top());
sumr-=r.top();
suml+=r.top();
r.pop();
}
while(l.size()>r.size()+1){
r.push(l.top());
suml-=l.top();
sumr+=l.top();
l.pop();
}
}
int qry(){
if(l.size()>r.size())return ((l.top()*l.size())-suml)+(sumr-(l.top()*r.size()));
else return (sumr-(r.top()*r.size()))+((r.top()*l.size())-suml);
}
int getmed(){
if(l.empty()&&r.empty())return inf;
if(l.size()>r.size())return l.top();
else return r.top();
}
void init(){
while(!l.empty())l.pop();
while(!r.empty())r.pop();
suml=0;
sumr=0;
med=0;
}
}t;
int k,n;
int pref[mxn+10];
bool cmp(pii a,pii b){return a.s<b.s;}
int32_t main(){
fastio
cin>>k>>n;
int ans=0;
vector<pii>v;
pair<char,int>a,b;
t.init();
for(int i=0;i<n;i++){
cin>>a.f>>a.s>>b.f>>b.s;
if(a.f==b.f)ans+=abs(a.s-b.s);
else v.pb({min(a.s,b.s),max(a.s,b.s)}),ans++;
}
sort(all(v),cmp);
t.init();
int add=inf;
for(int i=0;i<v.size();i++){
t.add(v[i].f);
t.add(v[i].s);
pref[i]=t.qry();
add=pref[i];
}
if(k==1)return cout<<add+ans,0;
t.init();
for(int i=v.size()-1;i>1;i--){
t.add(v[i].f);
t.add(v[i].s);
add=min(add,t.qry()+pref[i-1]);
}
cout<<ans+add;
}
Compilation message
bridge.cpp: In function 'int32_t main()':
bridge.cpp:91:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
