/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#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;
vector<pair<pair<int, int>, int> > sti, stj;
void addi(int id) {
fi.insert({vx[r[id]], id});
sti.pb({{vx[r[id]], id}, 1});
sumi += vx[r[id]];
cnti++;
}
void addj(int id) {
fj.insert({vx[l[id]], id});
stj.pb({{vx[l[id]], id}, 1});
sumj += vx[l[id]];
cntj++;
}
void deli(int id) {
if (fi.find({vx[r[id]], id}) != fi.end()) {
cnti--;
sumi -= vx[r[id]];
sti.pb({{vx[r[id]], id}, -1});
fi.erase({vx[r[id]], id});
}
}
void updi(int x) {
while (!fi.empty()) {
auto y = *fi.rbegin();
if (y.first >= x) {
fi.erase(y);
sti.pb({y, -1});
cnti--;
sumi -= y.first;
} else {
break;
}
}
}
void updj(int x) {
while (!fj.empty()) {
auto y = *fj.begin();
if (y.first <= x) {
fj.erase(y);
stj.pb({y, -1});
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)) {
long long cur = getres(i, uk);
int ft1 = ft;
long long si, sj, ci, cj;
si = sumi;
ci = cnti;
sj = sumj;
cj = cntj;
uk++;
recalc(i, uk);
long long cur1 = getres(i, uk);
if (cur1 <= cur) {
continue;
}
sumi = si;
cnti = ci;
cntj = cj;
sumj = sj;
ft = ft1;
for (int k = sz(sti) - 1; k >= 0; k--) {
auto x = sti[k].first;
int t = sti[k].second;
if (t == 1) {
fi.erase(x);
} else {
fi.insert(x);
}
}
sti.clear();
for (int k = sz(stj) - 1; k >= 0; k--) {
auto x = stj[k].first;
int t = stj[k].second;
if (t == 1) {
fj.erase(x);
} else {
fj.insert(x);
}
}
stj.clear();
uk--;
break;
}
chkmin(add, getres(i, uk));
}
cout << ans + 2 * add << '\n';
return 0;
}
# |
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 |
Correct |
11 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9848 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
10 ms |
9852 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
10 ms |
9720 KB |
Output is correct |
11 |
Correct |
11 ms |
9852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9724 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9848 KB |
Output is correct |
4 |
Correct |
10 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9840 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
12 ms |
9848 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
13 ms |
9720 KB |
Output is correct |
11 |
Correct |
11 ms |
9848 KB |
Output is correct |
12 |
Correct |
43 ms |
12908 KB |
Output is correct |
13 |
Correct |
134 ms |
19180 KB |
Output is correct |
14 |
Correct |
77 ms |
12784 KB |
Output is correct |
15 |
Correct |
76 ms |
15344 KB |
Output is correct |
16 |
Correct |
45 ms |
12652 KB |
Output is correct |
17 |
Correct |
94 ms |
19184 KB |
Output is correct |
18 |
Correct |
82 ms |
19152 KB |
Output is correct |
19 |
Correct |
132 ms |
19052 KB |
Output is correct |
20 |
Correct |
50 ms |
12652 KB |
Output is correct |
21 |
Correct |
94 ms |
19184 KB |
Output is correct |
# |
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 |
9724 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 |
9720 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 |
9724 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9720 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |