이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///
/// ♪ 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 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... |