/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 200228;
int n, k;
int l[MAXN], r[MAXN];
int st[MAXN];
vector<int> fb[MAXN];
vector<int> fe[MAXN];
long long score[MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//read(FILENAME);
cin >> k >> n;
long long ans = 0;
int uk = 0;
for (int i = 0; i < n; i++) {
char c, c1;
int x, x1;
cin >> c >> x >> c1 >> x1;
if (c == c1) {
ans += abs(x1 - x);
continue;
}
if (x > x1) {
swap(x, x1);
}
ans += x1 - x + 1;
l[uk] = x;
r[uk] = x1;
uk++;
}
n = uk;
vector<int> vx;
for (int i = 0; i < n; i++) {
vx.pb(l[i]);
vx.pb(r[i]);
}
sort(all(vx));
vx.resize(distance(vx.begin(), unique(all(vx))));
for (int i = 0; i < n; i++) {
l[i] = lower_bound(all(vx), l[i]) - vx.begin();
r[i] = lower_bound(all(vx), r[i]) - vx.begin();
}
if (k == 1) {
for (int i = 0; i < n; i++) {
fb[l[i]].pb(i);
fe[r[i]].pb(i);
//cout << l[i] << ' ' << r[i] << endl;
}
long long sum = 0;
int cnt = 0;
for (int i = 0; i < sz(vx); i++) {
for (auto x: fe[i]) {
sum += vx[r[x]];
cnt++;
}
score[i] += 1LL * vx[i] * cnt - sum;
}
cnt = 0;
sum = 0;
long long add = 2e18;
for (int i = sz(vx) - 1; i >= 0; i--) {
for (auto x: fb[i]) {
sum += vx[l[x]];
cnt++;
}
score[i] += -1LL * vx[i] * cnt + sum;
chkmin(add, score[i]);
}
//cout << add << endl;
cout << ans + 2 * add << '\n';
return 0;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
