#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int tt;cin >> tt;while (tt--) solve();
int k,n,cnt;
long long offset = 0;
pair <int,int> segment[100009];
namespace sub1 {
bool check() {
return k == 1 && n <= 1000;
}
long long cal(int point) {
long long ret = 0;
for (int i = 1;i <= n;i++) {
ret += abs(segment[i].first - point) + abs(segment[i].second - point);
}
return ret;
}
void solve() {
if (n == 0) {
cout << offset;
return ;
}
long long curr = 1e18;
for (int i = 1;i <= n;i++) {
curr = min({curr,cal(segment[i].first),cal(segment[i].second)});
}
cout << curr + offset << '\n';
}
}
namespace sub2 {
bool check() {
return k == 1 && n <= 100000;
}
int points[200009];
long long ans[200009],ans2[200009];
void solve() {
if (n == 0) {
cout << offset;
return ;
}
long long total = 0;
for (int i = 1;i <= n;i++) {
points[i] = segment[i].first;
points[i + n] = segment[i].second;
total += segment[i].second - segment[i].first;
}
sort(points + 1,points + 1 + 2*n);
sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) {
return a.second < b.second;
});
long long curr = 0,curr2 = 0;
int pt = 0;
for (int i = 1;i <= 2*n;i++) {
while (pt < n && segment[pt + 1].second < points[i]) {
pt++;
curr2 += segment[pt].second - segment[pt].first;
curr += segment[pt].second + segment[pt].first;
}
ans2[i] += curr2;
ans[i] += 2ll*pt*points[i] - curr;
}
sort(segment + 1,segment + 1 + n,[] (pair <int,int> a,pair <int,int> b) {
return a.first < b.first;
});
curr = curr2 = 0;
pt = n + 1;
for (int i = 2*n;i >= 1;i--) {
while (pt > 1 && segment[pt - 1].first > points[i]) {
pt--;
curr2 += segment[pt].second - segment[pt].first;
curr += segment[pt].second + segment[pt].first;
}
ans2[i] += curr2;
ans[i] += curr - 2ll*(n - pt + 1)*points[i];
}
long long ret = 1e18;
for (int i = 1;i <= 2*n;i++) {
ret = min(ret,ans[i] + total - ans2[i]);
}
cout << ret + offset << '\n';
}
}
namespace sub3 {
bool check() {
return k == 2 && n <= 100;
}
int pt[209];
long long cal(int point,int point2) {
long long ret = 0;
for (int i = 1;i <= n;i++) {
ret += min({abs(segment[i].first - point) + abs(segment[i].second - point),
abs(segment[i].first - point2) + abs(segment[i].second - point2)});
}
return ret;
}
void solve() {
if (n == 0) {
cout << offset;
return ;
}
long long curr = 1e18;
for (int i = 1;i <= n;i++) {
pt[i] = segment[i].first;
pt[i + n] = segment[i].second;
}
for (int i = 1;i <= 2*n;i++) {
for (int j = i + 1;j <= 2*n;j++) {
curr = min(curr,cal(pt[i],pt[j]));
}
}
cout << curr + offset << '\n';
}
}
int main() {
// FastIO
// MULTEST
// freopen("bridges.inp","r",stdin);
// freopen("bridges.out","w",stdout);
cin >> k >> n;
for (int i = 1;i <= n;i++) {
char _1,_2;int __1,__2;
cin >> _1 >> __1 >> _2 >> __2;
if (_1 == _2) offset += abs(__2 - __1);
else {
segment[++cnt] = {__1,__2};
offset++;
if (segment[cnt].first > segment[cnt].second) swap(segment[cnt].first,segment[cnt].second);
}
}
n = cnt;
if (sub1::check()) {
sub1::solve();
return 0;
}
if (sub2::check()) {
sub2::solve();
return 0;
}
if (sub3::check()) {
sub3::solve();
return 0;
}
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
# | 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... |