이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
int n, K, sum;
int b[MX];
int c[MX];
pii a[MX];
pii Q[MX];
vector<int> id;
void nhap(){
cin >> K >> n;
int t = 0;
for(int i=1; i<=n; i++){
int l, r; char t1, t2;
cin >> t1 >> l >> t2 >> r;
if(l > r) swap(l, r);
sum += r-l;
if(t1 != t2) a[++t] = {l, r};
}
n = t;
sum += n;
if(n==0) cout << sum, exit(0);
}
int lower_bound_B(int x){
int res = 0;
for(int lo=1, hi=n; lo<=hi;){
int mid = (lo+hi)>>1;
if(b[mid] - b[mid-1] <= x) res = mid, lo = mid + 1;
else hi = mid - 1;
}
return res;
}
void subK1(){
int l=0, r=1;
int res = OO;
for(int x: id){
while(l<n && b[l+1] - b[l] <= x) l++;
while(r<=n && c[r] - c[r+1] <= x) r++;
res = min(res, (x*l - b[l] + c[r] - x*(n-r+1))*2);
}
cout << res + sum;
}
int calc(int mid){
int res = OO, cur = 0;
int qID = 0;
cur = id[mid]*(lower_bound_B(id[mid])) - b[lower_bound_B(id[mid])];
for(int i=1; i<=n; i++) if(a[i].fi>id[mid]){
Q[++qID] = {a[i].se + a[i].fi - id[mid], a[i].se};
cur += a[i].fi - id[mid];
}
sort(Q+1, Q+1+qID);
int j = n+1;
int Extra = 0;
priority_queue<int, vector<int>, greater<int>> extraQ;
for(int i=(int)id.size()-1; i>mid; i--){
while(qID && Q[qID].fi - id[i] >= 0){
cur = cur - (Q[qID].fi - Q[qID].se) + id[i] - Q[qID].se + Extra;
extraQ.push(id[i] - Q[qID].se + Extra);
qID--;
}
while(extraQ.size() && extraQ.top() <= Extra){
cur -= extraQ.top();
extraQ.pop();
}
while(c[j-1] - c[j] >= id[i]) j--;
res = min(res, cur - Extra*(int)extraQ.size() + c[j] - id[i]*(n-j+1) );
Extra += id[i] - id[i-1];
}
return res*2;
}
void subK2(){
int res = OO;
for(int lo=0, hi=(int)id.size()/2; lo<=hi;){
int mid = (lo+hi)>>1;
if(lo+1>=hi){
res = min({res, calc(lo), calc(hi)});
break;
}
int cost1 = calc(mid-1);
int cost2 = calc(mid+1);
if(cost1 < cost2) res = min(res, cost1), hi = mid;
if(cost1 > cost2) res = min(res, cost2), lo = mid;
if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
}
for(int lo=(int)id.size()/4 + 1, hi=(int)id.size()/2; lo<=hi;){
int mid = (lo+hi)>>1;
if(lo+1>=hi){
res = min({res, calc(lo), calc(hi)});
break;
}
int cost1 = calc(mid-1);
int cost2 = calc(mid+1);
if(cost1 < cost2) res = min(res, cost1), hi = mid;
if(cost1 > cost2) res = min(res, cost2), lo = mid;
if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
}
// for(int lo=(int)id.size()/2, hi=(int)id.size()/4*3; lo<=hi;){
// int mid = (lo+hi)>>1;
// if(lo+1>=hi){
// res = min({res, calc(lo), calc(hi)});
// break;
// }
// int cost1 = calc(mid-1);
// int cost2 = calc(mid+1);
// if(cost1 < cost2) res = min(res, cost1), hi = mid;
// if(cost1 > cost2) res = min(res, cost2), lo = mid;
// if(cost1 == cost2) res = min(res, calc(mid)), lo=hi+1;
// }
cout << res + sum << endl;
}
void solve(){
id.resize(n+n);
for(int i=1; i<=n; i++){
id[i-1] = a[i].fi;
id[i+n-1] = a[i].se;
b[i] = a[i].se;
c[i] = a[i].fi;
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
sort(a+1, a+1+n);
sort(b+1, b+1+n);
sort(c+1, c+1+n);
for(int i=1; i<=n; i++) b[i] += b[i-1];
for(int i=n; i>=1; i--) c[i] += c[i+1];
if(K==1){
subK1();
return;
}
if(K==2){
subK2();
return;
}
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
/**
2 6
A 1 B 3
A 2 B 4
A 3 B 5
A 4 B 6
A 5 B 7
A 6 B 8
**/
# | 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... |