#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 1e18;
int tuf = (int)2e9 + 1;
const int NN = 5e6;
int n,k;
char p[100005],q[100005];
int s[100005],t[100005];
int ans;
int real_value[200005];
int m;
int cate_r[200005],sum_r[200005],cate_l[200005],sum_l[200005];
void normalize()
{
set<int> vls;
for (int i = 1; i <= n; i++)
{
vls.insert(s[i]);
vls.insert(t[i]);
}
map<int,int> norma;
int itr = 0;
for (auto it : vls)
{
itr++;
norma[it] = itr;
real_value[itr] = it;
}
m = itr;
for (int i = 1; i <= n; i++)
s[i] = norma[s[i]],t[i] = norma[t[i]];
}
int y_opt[200005];
pair<int,int> aint[NN + 5];
int fs[NN + 5],fd[NN + 5];
int roots1[200005],roots2[200005];
int cate;
pair<int,int> query(int nod, int l, int r, int st, int dr)
{
if (aint[nod].first == 0)
return aint[nod];
if (r < st or dr < l)
return {0,0};
if (st <= l and r <= dr)
return aint[nod];
int mij = (l + r) / 2;
pair<int,int> p1 = query(fs[nod],l,mij,st,dr),p2 = query(fd[nod],mij + 1,r,st,dr);
return {p1.first + p2.first,p1.second + p2.second};
}
void update(int nod, int l, int r, int pos, int val)
{
if (l == r)
{
aint[nod].first++;
aint[nod].second += val;
}
else
{
int mij = (l + r) / 2;
if (pos <= mij)
{
cate++;
aint[cate] = aint[fs[nod]];
fs[cate] = fs[fs[nod]];
fd[cate] = fd[fd[nod]];
fs[nod] = cate;
update(fs[nod],l,mij,pos,val);
}
else
{
cate++;
aint[cate] = aint[fd[nod]];
fs[cate] = fs[fd[nod]];
fd[cate] = fd[fd[nod]];
fd[nod] = cate;
update(fd[nod],mij + 1,r,pos,val);
}
aint[nod] = {aint[fs[nod]].first + aint[fd[nod]].first,aint[fs[nod]].second + aint[fd[nod]].second};
}
}
int f(int x,int y)
{
int dev = 0;
dev += real_value[x] * cate_r[x - 1] - sum_r[x - 1];
dev += sum_l[y + 1] - real_value[y] * cate_l[y + 1];
pair<int,int> p1 = query(roots1[x],0,tuf,0,real_value[x] + real_value[y]);///.first = cate, .second = suma L-urilor reale
pair<int,int> p2 = query(roots2[y],0,tuf,real_value[x] + real_value[y] + 1,tuf);///.first = cate, .second = suma R-urilor reale
dev += p1.second - p1.first * real_value[x];
dev += p2.first * real_value[y] - p2.second;
dev *= 2;
return dev;
}
void solve(int l, int r, int st, int dr)
{
if (l > r)
return;
int mij = (l + r) / 2;
int bst = inf;
for (int i = st; i <= dr; i++)
{
int cat = f(mij,i);
if (cat < bst)
{
bst = cat;
y_opt[mij] = i;
}
}
solve(l,mij - 1,st,y_opt[mij]);
solve(mij + 1,r,y_opt[mij],dr);
}
vector<pair<int,int>> cine_r[200005],cine_l[200005];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i] >> s[i] >> q[i] >> t[i];
if (s[i] > t[i])
swap(s[i],t[i]);
ans += t[i] - s[i];
if (p[i] == q[i])
n--,i--;
}
ans += n;
if (n <= k)
{
cout << ans << '\n';
return 0;
}
normalize();
for (int i = 1; i <= n; i++)
{
cine_l[s[i]].push_back({s[i],t[i]});
cine_r[t[i]].push_back({s[i],t[i]});
}
for (int i = 1; i <= n; i++)
{
cate_r[t[i] + 1]++;
sum_r[t[i] + 1] += real_value[t[i]];
cate_l[s[i] - 1]++;
sum_l[s[i] - 1] += real_value[s[i]];
}
for (int i = 1; i <= m; i++)
{
cate_r[i] += cate_r[i - 1];
sum_r[i] += sum_r[i - 1];
}
for (int i = m; i >= 1; i--)
{
cate_l[i] += cate_l[i + 1];
sum_l[i] += sum_l[i + 1];
}
if (k == 1)
{
int devmin = inf;
for (int i = 1; i <= m; i++)
{
int cr = cate_r[i - 1],sr = sum_r[i - 1],cl = cate_l[i + 1],sl = sum_l[i + 1];
int x = real_value[i];
int dev = 2 * (x * cr - sr + sl - x * cl);
devmin = min(devmin,dev);
}
cout << ans + devmin;
}
else
{
cate = 2 * m;
for (int i = 1; i <= m; i++)
roots1[i] = i;
for (int i = 1; i <= m; i++)
roots2[i] = i + m;
for (int x = m; x >= 1; x--)
{
aint[x] = aint[x + 1];
fs[x] = fs[x + 1];
fd[x] = fd[x + 1];
for (auto interval : cine_l[x + 1])
update(x,0,tuf,real_value[interval.first] + real_value[interval.second],real_value[interval.first]);
}
for (int y = m + 1; y <= 2 * m; y++)
{
if (y != m + 1)
{
aint[y] = aint[y - 1];
fs[y] = fs[y - 1];
fd[y] = fd[y - 1];
}
for (auto interval : cine_r[y - m - 1])
update(y,0,tuf,real_value[interval.first] + real_value[interval.second],real_value[interval.second]);
}
solve(1,m,1,m);
int devmin = inf;
for (int i = 1; i <= m; i++)
devmin = min(devmin,f(i,y_opt[i]));
cout << ans + devmin;
}
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
/**
Obs: merita sa fac pod doar unde e cv cladire, adica in O(N) locatii
Initial adun abs(S[i] - T[i]) la toate, fac S[i] <= T[i], daca P[i] = Q[i] il elimin, altfel mai adaug 1 si presupun P[i] = A, Q[i] = B
N o sa fie cate intervale au P[i] != Q[i]
K = 1 -> fixez unde fac podul, vad cate au R in stanga si suma R-urilor, cate au L in dreapta si suma L-urilor, cv formula
K = 2
Fie x si y locatiile (dintre cele O(N)) in care imi fac podurile
Cred (doamne ajuta adica) ca daca imi fixez un x, y_opt(x) e crescator (divide dp stuff)
Hai sa zicem ca am eu o functie magica f(x,y) care imi calculeaza suma devierilor daca fac poduri in x si y
Pai f(x,y) functioneaza gen: ia toate alea cu R < x si zice cate si suma, toate cu L > y si zice cate si suma etc penal
Problema apare la alea x < L <= R < y ca am min(L - x, y - R)
Aici, zic asa: fie mij = r[x] + r[y] (omit / 2 ca nu conteaza) si m = r[L] + r[R]
Daca m <= mij, L - x e minim, altfel R - y e minim
Atunci f(x,y) zice: gaseste toti aia cu L > x si m <= mij si zi cati si suma L-urilor (oricum asta imi garanteaza y < R)
Apoi, gaseste toti aia cu R < y si m > mij si zi cati si suma R-urilor (once again, asta garanteaza L > x)
In functie de chestiile alea am o formula penala pentru f(x,y)
Pai nu am update-uri sau ceva, deci pot sa ma uit asa:
- pentru alea cu R < x, doar imi tin ceva cate_r[x] si sum_r[x] (cate r < x si suma valorilor lor reale)
- pentru alea cu L > y, ceva analog pe sufixe
- pentru cate L > x si m <= mij, dat fiind ca nu am update-uri pot sa ma uit in versiunea x si sa intreb chestii pe m <= mij
Adica sa imi tin un aint persistent in care merg cu x de la m la 1 si imi tin pentru fiecare, structura pe alea cu L mai mare
-pentru R < y, m > mij, tot asa, un aint persistent de merg cu y de la 1 la m si tin strucura pe m cu alea cu R < y
Astfel, am o precalculare O(NlogN) timp si memorie si O(logN) timp pe query, deci Nlog^2 total
Hai ca mai stie cineva sa implementeze aint persistent
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12932 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19036 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
23432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
23388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
23132 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
23388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
