제출 #550015

#제출 시각아이디문제언어결과실행 시간메모리
550015CyberSleeperPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms468 KiB
#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(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; } 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; } } void ins(ll x, ll idx){ if(L[idx].empty() || x<=*L[idx].rbegin()){ L[idx].insert(x); sumL[idx]+=x; }else{ 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...