#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
#include <complex>
#include <array>
#include <utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
#define F first
#define S second
const double eps = 1e-12;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
vll cost(ll n,vll &a,vll &b){
priority_queue<ll> left; // including median
priority_queue<ll,vll,greater<ll>> right; // excluding median
ll suml = 0;
ll sumr = 0;
vll ans;
if(a[0]<=b[0]) swap(a[0],b[0]);
left.push(b[0]);
right.push(a[0]);
sumr += a[0];
suml += b[0];
ans.push_back(0);
FOR(i,1,n){
ll med = left.top();
ans.push_back(sumr-suml);
if(a[i]>med){
if(b[i]>med){
right.push(a[i]);
right.push(b[i]);
sumr += (a[i]+b[i]);
left.push(right.top());
suml += right.top();
sumr -= right.top();
right.pop();
}
else{
right.push(a[i]);
sumr += a[i];
left.push(b[i]);
suml += b[i];
}
}
else{
if(b[i]<=med){
left.push(a[i]);
left.push(b[i]);
suml += (a[i]+b[i]);
right.push(left.top());
sumr += left.top();
suml -= left.top();
left.pop();
}
else{
right.push(b[i]);
sumr += b[i];
left.push(a[i]);
suml += a[i];
}
}
}
ans.push_back(sumr-suml);
return ans;
}
void solve(){
// store very big numbers may mean log2.
// A comparator must return false for two equal objects. Not doing so results in undefined behavior.
ll k,n;
cin >> k >> n;
vll a;
vll b;
ll ans = 0;
FOR(i,0,n){
char p,q;
ll s,t;
cin >> p >> s >> q >> t;
if(p==q){
ans += abs(s-t);
}
else{
a.push_back(s);
b.push_back(t);
}
}
n = a.size();
if(n==0){
cout << ans << "\n";
return;
}
if(k==1){
vll left = cost(n,a,b);
cout << (ans+left[n]+n) << "\n";
}
else{
vector<pll> c;
FOR(i,0,n){
c.push_back({a[i]+b[i],i});
}
sort(all(c));
vll a1;
vll b1;
FOR(i,0,n){
a1.push_back(a[c[i].S]);
b1.push_back(b[c[i].S]);
}
vll left = cost(n,a1,b1);
reverse(all(a1));
reverse(all(b1));
vll right = cost(n,a1,b1);
ll curr_ans = 1e16;
FOR(i,0,n+1){
curr_ans = min(curr_ans,left[i]+right[n-i]);
}
cout << (ans+curr_ans+n) << "\n";
}
}
signed main(){
//setIO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// init_code();
ll t=1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'void init_code()':
bridge.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |