/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#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];
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]);
}
vx.pb(0);
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 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9724 KB |
Output is correct |
3 |
Correct |
10 ms |
9848 KB |
Output is correct |
4 |
Correct |
11 ms |
9848 KB |
Output is correct |
5 |
Correct |
13 ms |
9976 KB |
Output is correct |
6 |
Correct |
13 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9848 KB |
Output is correct |
9 |
Correct |
19 ms |
9848 KB |
Output is correct |
10 |
Correct |
12 ms |
9848 KB |
Output is correct |
11 |
Correct |
13 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9848 KB |
Output is correct |
5 |
Correct |
10 ms |
9848 KB |
Output is correct |
6 |
Correct |
10 ms |
9848 KB |
Output is correct |
7 |
Correct |
10 ms |
9848 KB |
Output is correct |
8 |
Correct |
13 ms |
9848 KB |
Output is correct |
9 |
Correct |
11 ms |
9892 KB |
Output is correct |
10 |
Correct |
13 ms |
9848 KB |
Output is correct |
11 |
Correct |
10 ms |
9848 KB |
Output is correct |
12 |
Correct |
40 ms |
13676 KB |
Output is correct |
13 |
Correct |
132 ms |
21488 KB |
Output is correct |
14 |
Correct |
80 ms |
14060 KB |
Output is correct |
15 |
Correct |
81 ms |
16628 KB |
Output is correct |
16 |
Correct |
46 ms |
14316 KB |
Output is correct |
17 |
Correct |
106 ms |
21488 KB |
Output is correct |
18 |
Correct |
83 ms |
21152 KB |
Output is correct |
19 |
Correct |
139 ms |
21428 KB |
Output is correct |
20 |
Correct |
51 ms |
14572 KB |
Output is correct |
21 |
Correct |
94 ms |
21228 KB |
Output is correct |
# |
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 |
- |