/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#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];
vector<int> vx;
int where[MAXN];
vector<pair<int, int> > st;
int ft = 0;
set<pair<int, int> > fi, fj;
int cnti = 0;
int cntj = 0;
long long sumi = 0;
long long sumj = 0;
void addi(int id) {
fi.insert({vx[r[id]], id});
sumi += vx[r[id]];
cnti++;
}
void addj(int id) {
fj.insert({vx[l[id]], id});
sumj += vx[l[id]];
cntj++;
}
void deli(int id) {
if (fi.find({vx[r[id]], id}) != fi.end()) {
cnti--;
sumi -= vx[r[id]];
fi.erase({vx[r[id]], id});
}
}
void updi(int x) {
while (!fi.empty()) {
auto y = *fi.rbegin();
if (y.first >= x) {
fi.erase(y);
cnti--;
sumi -= y.first;
} else {
break;
}
}
}
void updj(int x) {
while (!fj.empty()) {
auto y = *fj.begin();
if (y.first <= x) {
fj.erase(y);
cntj--;
sumj -= y.first;
} else {
break;
}
}
}
void recalc(int i, int j) {
i = vx[i];
j = vx[j];
while (ft < sz(st) && st[ft].first < i + j) {
deli(st[ft].second);
addj(st[ft].second);
ft++;
}
updi(i);
updj(j);
}
long long geti(int x) {
return 1LL * x * cnti - sumi;
}
long long getj(int x) {
return -1LL * x * cntj + sumj;
}
long long getres(int i, int j) {
long long add = geti(vx[i]) + getj(vx[j]);
return add;
}
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;
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;
}
uk = 0;
ft = 0;
long long add = 2e18;
for (int i = 0; i < n; i++) {
//x - r[i] <= l[i] - y
//x + y <= l[i] + r[i]
st.pb({vx[l[i]] + vx[r[i]], i});
}
sort(all(st));
for (int i = 0; i < n; i++) {
where[st[i].second] = i;
addi(i);
}
for (int i = 0; i < sz(vx); i++) {
chkmax(uk, i);
recalc(i, uk);
while (uk + 1 < sz(vx) && getres(i, uk) >= getres(i, uk + 1)) {
uk++;
recalc(i, uk);
}
chkmin(add, getres(i, uk));
}
cout << ans + 2 * add << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
9720 KB |
Output is correct |
2 |
Correct |
12 ms |
9720 KB |
Output is correct |
3 |
Correct |
13 ms |
9852 KB |
Output is correct |
4 |
Correct |
13 ms |
9848 KB |
Output is correct |
5 |
Correct |
12 ms |
9848 KB |
Output is correct |
6 |
Correct |
12 ms |
9848 KB |
Output is correct |
7 |
Correct |
14 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9848 KB |
Output is correct |
9 |
Correct |
11 ms |
9852 KB |
Output is correct |
10 |
Correct |
11 ms |
9848 KB |
Output is correct |
11 |
Correct |
11 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9592 KB |
Output is correct |
2 |
Correct |
10 ms |
9724 KB |
Output is correct |
3 |
Correct |
11 ms |
9848 KB |
Output is correct |
4 |
Correct |
11 ms |
9848 KB |
Output is correct |
5 |
Correct |
12 ms |
9848 KB |
Output is correct |
6 |
Correct |
10 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 |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
10 ms |
9720 KB |
Output is correct |
11 |
Correct |
10 ms |
9848 KB |
Output is correct |
12 |
Correct |
40 ms |
12912 KB |
Output is correct |
13 |
Correct |
136 ms |
19156 KB |
Output is correct |
14 |
Correct |
80 ms |
12772 KB |
Output is correct |
15 |
Correct |
76 ms |
15348 KB |
Output is correct |
16 |
Correct |
45 ms |
12528 KB |
Output is correct |
17 |
Correct |
93 ms |
19180 KB |
Output is correct |
18 |
Correct |
82 ms |
19184 KB |
Output is correct |
19 |
Correct |
141 ms |
19028 KB |
Output is correct |
20 |
Correct |
51 ms |
12656 KB |
Output is correct |
21 |
Correct |
94 ms |
19308 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 |
9792 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9848 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9848 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9820 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
9848 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9848 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |