This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x) cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ld long double
#define nl endl
#define tb '\t'
#define sp ' '
#define sqr(x) (x)*(x)
#define arr3 array<int, 3>
using namespace std;
const int MX=30005, MOD=1000000007, BLOCK=160, INF=2e9+7, LG=62;
const ll INFF=1000000000000000007;
const ld ERR=1e-6, pi=3.14159265358979323846;
ll N, K, ans, sumL[2], sumR[2], best;
multiset<ll> L[2], R[2];
vector<pll> A;
void balance(int idx){
while(L[idx].size() && L[idx].size()-1>R[idx].size()){
ll tmp=*L[idx].rbegin();
L[idx].erase(prev(L[idx].end()));
R[idx].insert(tmp);
sumL[idx]-=tmp;
sumR[idx]+=tmp;
}
while(R[idx].size() && L[idx].size()<R[idx].size()){
ll tmp=*R[idx].begin();
R[idx].erase(R[idx].begin());
L[idx].insert(tmp);
sumR[idx]-=tmp;
sumL[idx]+=tmp;
}
}
void ins(ll x, ll idx){
R[idx].insert(x);
sumR[idx]+=x;
balance(idx);
}
void era(ll x, ll idx){
if(R[idx].count(x)){
R[idx].erase(R[idx].find(x));
sumR[idx]-=x;
}else{
L[idx].erase(L[idx].find(x));
sumL[idx]-=x;
}
balance(idx);
}
ll comp(ll x, ll y){
return (L[x].size()*y-sumL[x]) + (sumR[x]-R[x].size()*y);
}
int main(){
fastio;
cin >> K >> N;
for(int i=0; i<N; i++){
char a, c;
int b, d;
cin >> a >> b >> c >> d;
if(a==c){
ans+=abs(b-d);
}else{
ans++;
if(a=='B')
swap(b, d);
A.pb({b+d, min(b, d)});
}
}
sort(all(A));
N=A.size();
for(int i=0; i<N; i++){
ll op=A[i].se, ed=A[i].fi-A[i].se;
ins(op, 1);
ins(ed, 1);
}
best=comp(1, *L[1].rbegin());
if(R[1].size())
best=min(best, comp(1, *R[1].begin()));
if(K==2){
for(int i=0; i<N; i++){
ll op=A[i].se, ed=A[i].fi-A[i].se;
ins(op, 0);
ins(ed, 0);
era(op, 1);
era(ed, 1);
if(L[0].size() && L[1].size())
best=min(best, comp(0, *L[0].rbegin()) + comp(1, *L[1].rbegin()));
if(R[0].size() && L[1].size())
best=min(best, comp(0, *R[0].begin()) + comp(1, *L[1].rbegin()));
if(L[0].size() && R[1].size())
best=min(best, comp(0, *L[0].rbegin()) + comp(1, *R[1].begin()));
if(R[0].size() && R[1].size())
best=min(best, comp(0, *R[0].begin()) + comp(1, *R[1].begin()));
}
}
cout << ans+best << nl;
}
# | 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... |