#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
struct type {
char c1; int x1;
char c2; int x2;
} person[maxN];
int k, n;
long long ans = 0;
void subtask1() {
vector<int> val;
for (int i = 1; i <= n; i++) {
val.push_back(person[i].x1);
val.push_back(person[i].x2);
}
sort(val.begin(), val.end());
int median = val[int(val.size() - 1) / 2];
//cout << median << '\n';
for (int i = 1; i <= n; i++)
ans += abs(person[i].x1 - median) + abs(person[i].x2 - median) + 1;
cout << ans;
return ;
}
multiset<int> left1, right1, left2, right2;
long long sum_left1 = 0, sum_right1 = 0, sum_left2 = 0, sum_right2 = 0;
bool cmp(type a, type b) {
return (a.x1 + a.x2) < (b.x1 < b.x2);
}
void add_to_the_second(int i) {
right2.insert(person[i].x1);
right2.insert(person[i].x2);
sum_right2 += person[i].x1;
sum_right2 += person[i].x2;
int exchange = *right2.begin();
left2.insert(exchange);
right2.erase(right2.find(exchange));
sum_left2 += exchange;
sum_right2 -= exchange;
}
void delete_from_the_second(int i) {
int x1 = person[i].x1, x2 = person[i].x2;
int med_right = *right2.begin();
/// Erase x1 from the second set
if (x1 < med_right || right2.size() == 0) {
left2.erase(left2.find(x1));
sum_left2 -= x1;
}
else {
right2.erase(right2.find(x1));
sum_right2 -= x1;
}
med_right = (right2.size() > 0 ? *right2.begin() : 1e9 + 7);
/// Erase x2 from the second set
if (x2 < med_right) {
left2.erase(left2.find(x2));
sum_left2 -= x2;
}
else {
right2.erase(right2.find(x2));
sum_right2 -= x1;
}
if (left2.size() > right2.size()) {
auto it = left2.end(); it--;
int exchange = *it;
left2.erase(it);
right2.insert(exchange);
sum_left2 -= exchange;
sum_right2 += exchange;
}
else if (left2.size() < right2.size()) {
auto it = right2.begin();
int exchange = *it;
right2.erase(it);
left2.insert(exchange);
sum_left2 += exchange;
sum_right2 -= exchange;
}
}
void add_to_the_first(int i) {
int x1 = person[i].x1, x2 = person[i].x2;
right1.insert(x1);
right1.insert(x2);
sum_right1 += x1;
sum_right1 += x2;
int exchange = *right1.begin();
right1.erase(right1.find(exchange));
left1.insert(exchange);
sum_right1 -= exchange;
sum_left1 += exchange;
}
void subtask2() {
sort(person + 1, person + n + 1, cmp);
for (int i = 1; i <= n; i++)
add_to_the_second(i);
long long res = 1e18;
for (int i = 1; i <= n - 1; i++) {
delete_from_the_second(i);
add_to_the_first(i);
int median_first = *right1.begin();
int median_second = *right2.begin();
long long cal = (1LL * median_first * i - sum_left1) + (sum_right1 - 1LL * median_first * (1LL * i));
cal = cal + (1LL * median_second * (1LL * (n - i)) - sum_left2) + (sum_right2 - 1LL * median_second * (1LL * (n - i)));
res = min(res, cal);
}
cout << res + ans + n;
return ;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> k >> n;
for (int i = 1; i <= n; i++) {
char c1, c2;
int x1, x2;
cin >> c1 >> x1 >> c2 >> x2;
if (c1 == c2) {
ans = ans + abs(x1 - x2);
n--;
i--;
continue;
}
person[i] = {c1, x1, c2, x2};
}
if (k == 1) subtask1();
else subtask2();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
15 ms |
3188 KB |
Output is correct |
13 |
Correct |
31 ms |
3036 KB |
Output is correct |
14 |
Correct |
22 ms |
3032 KB |
Output is correct |
15 |
Correct |
18 ms |
2016 KB |
Output is correct |
16 |
Correct |
18 ms |
3036 KB |
Output is correct |
17 |
Correct |
21 ms |
3036 KB |
Output is correct |
18 |
Correct |
25 ms |
3036 KB |
Output is correct |
19 |
Correct |
30 ms |
3036 KB |
Output is correct |
20 |
Correct |
20 ms |
3036 KB |
Output is correct |
21 |
Correct |
27 ms |
2968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |