#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 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];
int ft = 0;
set<pair<int, int> > fi, fj, f1i, f1j, f2i;
int cnti = 0;
int cntj = 0;
long long sumi = 0;
long long sumj = 0;
int cnt1i = 0;
int cnt1j = 0;
long long sum1i = 0;
long long sum1j = 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 delj(int id) {
if (fj.find({vx[l[id]], id}) != fj.end()) {
cntj--;
sumj -= vx[l[id]];
stj.pb({{vx[l[id]], id}, -1});
fj.erase({vx[l[id]], id});
} else {
if (f1j.find({vx[r[id]], id}) != f1j.end()) {
stj.pb({{vx[r[id]], id}, -2});
f1j.erase({vx[r[id]], id});
} else {
cnt1j--;
sum1j -= vx[r[id]];
}
}
}
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});
}
if (f1i.find({vx[l[id]], id}) != f1i.end()) {
cnt1i--;
sum1i -= vx[l[id]];
//cout << cnt1i << ' ' << sum1i << endl;
sti.pb({{vx[l[id]], id}, -2});
f1i.erase({vx[l[id]], id});
}
if (f2i.find({vx[r[id]], id}) != f2i.end()) {
sti.pb({{vx[r[id]], id}, -3});
f2i.erase({vx[r[id]], id});
}
}
void updi(int x) {
//cout << x << endl;
while (!fi.empty()) {
auto y = *fi.rbegin();
if (y.first >= x) {
fi.erase(y);
sti.pb({y, -1});
cnti--;
sumi -= y.first;
if (vx[l[y.second]] > x) {
cnt1i++;
sum1i += vx[l[y.second]];
//cout << -x * cnt1i + sum1i << endl;
f1i.insert({vx[l[y.second]], y.second});
sti.pb({{vx[l[y.second]], y.second}, 2});
} else {
f2i.insert({vx[r[y.second]], y.second});
sti.pb({{vx[r[y.second]], y.second}, 3});
}
} else {
break;
}
}
//cout << sz(f1i) << ' ' << x << endl;
while (!f1i.empty()) {
auto y = *f1i.begin();
//cout << y.first << ' ' << x << endl;
if (y.first <= x) {
f1i.erase(y);
sti.pb({y, -2});
cnt1i--;
sum1i -= y.first;
//cout << -x * cnt1i + sum1i << endl;
f2i.insert({vx[r[y.second]], y.second});
sti.pb({{vx[r[y.second]], y.second}, 3});
} else {
break;
}
}
while (!f2i.empty()) {
auto y = *f2i.begin();
if (y.first < x) {
f2i.erase(y);
sti.pb({y, -3});
cnti++;
sumi += y.first;
} else {
break;
}
}
}
bool was[MAXN];
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;
if (vx[r[y.second]] < x) {
cnt1j++;
sum1j += vx[r[y.second]];
//cout << r[y.second] << endl;
//cout << cnt1j << ' ' << r[y.second] << ' ' << x << endl;
} else {
f1j.insert({vx[r[y.second]], y.second});
stj.pb({{vx[r[y.second]], y.second}, 2});
}
} else {
break;
}
}
while (!f1j.empty()) {
auto y = *f1j.begin();
if (y.first < x) {
f1j.erase(y);
stj.pb({y, -2});
cnt1j++;
//cout << cnt1j << ' ' << y.first << ' ' << x << endl;
sum1j += y.first;
//cout << cnt1j << endl;
} else {
break;
}
}
}
long long geti(int x) {
return 1LL * x * cnti - sumi -1LL * x * cnt1i + sum1i;
}
long long getj(int x) {
return -1LL * x * cntj + sumj + 1LL *x * cnt1j - sum1j;
}
vector<int> fs;
set<pair<int, int> > st;
vector<pair<int, int> > gg;
void recalc(int i, int j) {
i = vx[i];
j = vx[j];
// cout << j << endl;
//cout << st[ft].first << ' ' << vx[l[st[ft].second]] << endl;
while (!st.empty()) {
auto x = *st.begin();
if (x.first <= i + j) {
st.erase(x);
gg.pb(x);
if (!was[x.second]) {
delj(x.second);
addi(x.second);
was[x.second] = true;
fs.pb(x.second);
}
//}
ft++;
} else {
break;
}
}
updi(i);
updj(j);
//cout << sum1j << endl;
//if (i == 2 && j == 5) {
//cout << getj(5) << endl;
// }
}
long long getres(int i, int j) {
// cout << cnti + cntj + cnt1i + cnt1j << endl;
// cout << -1LL * vx[i] * cnt1i + sum1i << endl;
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, score9[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]
//cout << vx[l[i]] + vx[r[i]] << endl;
fb[l[i]].pb(i);
fe[r[i]].pb(i);
}
//l - x <= y - r
//l + r <= x + y;
for (int i = 0; i < n; i++) {
addj(i);
}
for (int i = 0; i < sz(vx); i++) {
for (auto x: fb[i]) {
if (!was[x]) {
delj(x);
addi(x);
st.erase({vx[l[x]] + vx[r[x]], x});
was[x] = true;
}
}
chkmax(uk, i);
recalc(i, uk);
//cout << cnt1i << endl;
sti.clear();
stj.clear();
fs.clear();
gg.clear();
// cout << vx[i] << endl;
while (uk + 1 < sz(vx)) {
long long cur = getres(i, uk);
//cout << sz(f1i) << endl;
int ft1 = ft;
long long si, sj, ci, cj;
si = sumi;
ci = cnti;
sj = sumj;
cj = cntj;
long long s1i, s1j, c1i, c1j;
s1i = sum1i;
c1i = cnt1i;
s1j = sum1j;
c1j = cnt1j;
vector<pair<int, int> > ff;
for (auto y: fe[uk]) {
if (was[y]) continue;
st.insert({vx[l[y]] + vx[r[y]], y});
ff.pb({vx[l[y]] + vx[r[y]], y});
}
uk++;
//cout << sz(sti) << endl;
recalc(i, uk);
long long cur1 = getres(i, uk);
//cout << cur << ' ' << cur1 << endl;
if (cur1 <= cur) {
sti.clear();
stj.clear();
fs.clear();
gg.clear();
continue;
}
//cout << cur << ' ' << cur1 << endl;
sumi = si;
cnti = ci;
cntj = cj;
sumj = sj;
sum1i = s1i;
cnt1i = c1i;
cnt1j = c1j;
sum1j = s1j;
//cout << sum1i - 1LL * vx[i] * cnt1i << ' ' << sum1i << ' ' << cnt1i << endl;
ft = ft1;
for (int k = sz(sti) - 1; k >= 0; k--) {
auto x = sti[k].first;
int t = sti[k].second;
if (t == 1 || t == -1) {
if (t == 1) {
fi.erase(x);
} else {
fi.insert(x);
}
} else if (t == 2 || t == -2) {
if (t == 2) {
f1i.erase(x);
} else {
f1i.insert(x);
}
} else {
if (t == 3) {
f2i.erase(x);
} else {
f2i.insert(x);
}
}
}
//cout << sz(f1i) << endl;
sti.clear();
for (int k = sz(stj) - 1; k >= 0; k--) {
auto x = stj[k].first;
int t = stj[k].second;
if (t == 1 || t == -1) {
if (t == 1) {
fj.erase(x);
} else {
fj.insert(x);
}
} else {
if (t == 2) {
f1j.erase(x);
} else {
f1j.insert(x);
}
}
}
stj.clear();
for (auto y: fs) {
was[y] = false;
}
for (auto y: gg) {
st.insert(y);
}
for (auto y: ff) {
st.erase(y);
}
fs.clear();
gg.clear();
uk--;
break;
}
//cout << sz(sti) << endl;
// cout << getres(i, uk) << endl;
// cout << vx[i] << ' ' << vx[uk] << endl;
chkmin(add, getres(i, uk));
}
//cout << add << endl;
cout << ans + 2 * add << '\n';
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:318:16: error: 'score9' was not declared in this scope
chkmin(add, score9[i]);
^~~~~~
bridge.cpp:318:16: note: suggested alternative: 'score'
chkmin(add, score9[i]);
^~~~~~
score
