제출 #477347

#제출 시각아이디문제언어결과실행 시간메모리
477347ymmPalembang Bridges (APIO15_bridge)C++17
100 / 100
150 ms9036 KiB
/// /// ♪ Let the voice of love take you higher! ♪ /// #include <bits/stdc++.h> #define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x) #define F first #define S second typedef long long ll; typedef std::pair<ll,ll> pll; using namespace std; ll inf = 1e9+100; const int N = 100010; pll a[N]; int k, n; vector<ll> stb; ll cntl[2*N], cntr[2*N]; #ifndef EVAL void dbg(){cout << "!\n";} template<class T, class... U> void dbg(T x, U... y){cout << x << ' '; dbg(y...);} #else template<class... T> void dbg(T... x){} #endif int main() { ios::sync_with_stdio(false); cin.tie(0); #ifndef EVAL freopen("in.txt", "r", stdin); #endif cin >> k >> n; ll stoneocean = 0; Loop(i,0,n) { char c1,c2; ll a1,a2; cin >> c1 >> a1; cin >> c2 >> a2; if(c1==c2) { stoneocean += abs(a1-a2); --i; --n; } else { a[i] = {a1,a2}; stb.push_back(a1); stb.push_back(a2); stoneocean += 1; } } if(n == 0) return cout << stoneocean << '\n', 0; sort(stb.begin(),stb.end()); stb.resize(unique(stb.begin(),stb.end())-stb.begin()); Loop(i,0,n) cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++, cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++; sort(a,a+n,[](pll& x, pll& y){return x.F+x.S < y.F+y.S;}); int p1 = 0, p2 = 0; ll c1 = 0, c2 = 2*n - 2*cntr[0]; ll suml = 0, sumr = -2*n*stb[0]; Loop(i,0,n) sumr += a[i].F+a[i].S; while(c2 > 0) { sumr -= c2*(stb[p2+1]-stb[p2]); ++p2; c2 -= 2*cntr[p2]; } if(k==1) return cout << stoneocean+sumr << '\n', 0; auto mov = [&](int i) -> void{ sumr -= abs(a[i].F-stb[p2]); sumr -= abs(a[i].S-stb[p2]); suml += abs(a[i].F-stb[p1]); suml += abs(a[i].S-stb[p1]); c2 -= a[i].F <= stb[p2]? -1: 1; c2 -= a[i].S <= stb[p2]? -1: 1; c1 += a[i].F <= stb[p1]? -1: 1; c1 += a[i].S <= stb[p1]? -1: 1; cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]--; cntl[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++; cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]--; cntl[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++; }; ll ans = suml+sumr; Loop(i,0,n) { mov(i); while(c2 > 0) { sumr -= c2*(stb[p2+1]-stb[p2]); ++p2; c2 -= 2*cntr[p2]; } while(c1 > 0) { suml -= c1*(stb[p1+1]-stb[p1]); ++p1; c1 -= 2*cntl[p1]; } ans = min(ans, suml+sumr); } cout << stoneocean+ans << '\n'; }
#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...