// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
using pii = pair<int, int>;
#ifdef LOCAL
const int N = 15;
#else
const int N = 100001;
#endif
const int inf = (int) 1e11;
int k, n;
int s[N], t[N];
bool f[N];
int calc(int x, int y = inf) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (f[i]) {
ans += min(abs(s[i] - x) + abs(t[i] - x) + 1, abs(s[i] - y) + abs(t[i] - y) + 1);
} else {
ans += abs(s[i] - t[i]);
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> k >> n;
vi pos;
for (int i = 0; i < n; i++) {
char a, b;
cin >> a >> s[i] >> b >> t[i];
pos.pb(s[i]);
pos.pb(t[i]);
f[i] = a!=b;
}
sort(all(pos));
pos.resize(unique(all(pos)) - pos.begin());
int m = (int) pos.size();
if (k == 1) {
int l = 0, r = m - 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (calc(pos[mid]) < calc(pos[mid + 1]))
r = mid;
else
l = mid;
}
int ans = LLONG_MAX;
for (int i = l; i <= r; i++)
ans = min(ans, calc(pos[i]));
cout << ans << '\n';
}
if (k == 2) {
auto Bebra = [&](int x) {
int ans = LLONG_MAX;
for (int i = 0; i < m; i++)
ans = min(ans, calc(pos[x], pos[i]));
return ans;
};
int l = 0, r = m - 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (Bebra(mid) < Bebra(mid+1))
r = mid;
else
l = mid;
}
int ans = LLONG_MAX;
for (int i = l; i <= r; i++)
ans = min(ans, Bebra(i));
cout << 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... |