#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();
struct DS{
struct node{
int s1; ll s2;
node *l, *r;
node(){
s1 = s2 = 0;
l = r = 0;
}
node(int x, ll y){
s1 = x; s2 = y;
l = r = 0;
}
node(node *ls, node *rs){
l = ls; r = rs;
s1 = s2 = 0;
if (l){
s1 += l -> s1;
s2 += l -> s2;
}
if (r){
s1 += r -> s1;
s2 += r -> s2;
}
}
};
node *rt;
int n;
void init(){
rt = new node();
n = 1e9;
}
node* upd(node *v, int tl, int tr, int& p, int& x){
if (tl == tr){
return new node(v -> s1 + 1, v -> s2 + x);
}
int tm = (tl + tr) / 2;
if (p <= tm){
if (!(v -> l)) v -> l = new node();
return new node(upd(v -> l, tl, tm, p, x), v -> r);
}
else {
if (!(v -> r)) v -> r = new node();
return new node(v -> l, upd(v -> r, tm + 1, tr, p, x));
}
}
void upd(int p, int x){
rt = upd(rt, 1, n, p, x);
}
pil get(node *v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return {0, 0};
if (l <= tl && tr <= r){
return {v -> s1, v -> s2};
}
int tm = (tl + tr) / 2;
pil p1 = {0, 0}, p2 = {0, 0};
if (v -> l) p1 = get(v -> l, tl, tm, l, r);
if (v -> r) p2 = get(v -> r, tm + 1, tr, l, r);
return {p1.ff + p2.ff, p1.ss + p2.ss};
}
pair<int, ll> get(int l, int r){
return get(rt, 1, n, l, r);
}
vector<int> all;
set<int> s1, s2;
void add(int x){
s1.insert(x);
if (s1.size() > s2.size()){
int y = *prev(s1.end());
s1.erase(s1.find(y));
s2.insert(y);
}
if (!s1.empty() && !s2.empty()){
int a = *prev(s1.end()), b = *s2.begin();
if (a > b){
s1.erase(s1.find(a));
s2.erase(s2.find(b));
s1.insert(b);
s2.insert(a);
}
}
upd(x, x);
}
ll get(){
if (s2.empty()) return 0;
int x = *s2.begin();
ll out = 0;
for (int i: all){
out += abs(i - x);
}
pil p1 = get(1, x), p2 = get(x + 1, n);
return (1LL * x * p1.ff - p1.ss) + (p2.ss - 1LL * x * p2.ff);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, n; cin>>k>>n;
vector<pii> all;
ll out = 0;
while (n--){
char t1, t2; int x1, y1; cin>>t1>>x1>>t2>>y1;
if (t1 == t2){
out += abs(x1 - y1);
continue;
}
if (x1 > y1) swap(x1, y1);
all.pb({x1, y1});
}
n = (int) all.size();
vector<int> imp;
for (int i = 0; i < n; i++){
imp.pb(all[i].ff); imp.pb(all[i].ss);
}
ll mn = inf;
if (k == 1){
vector<int> f;
for (auto [x, y]: all){
f.pb(x); f.pb(y);
}
sort(f.begin(), f.end());
int x = f[(int) (f.size() - 1) / 2];
ll sum = 0;
for (int i: f){
sum += abs(i - x);
}
mn = sum + n;
}
else {
ll S = 0;
for (auto [x, y]: all){
S += (y - x);
}
int h = (int) imp.size();
sort(imp.begin(), imp.end());
vector<ll> out1(h), out2(h), h1(h), h2(h);
vector<pii> p1(h), p2(h);
auto cmp = [&](pii x, pii y){
return x.ss < y.ss;
};
sort(all.begin(), all.end(), cmp);
int j = 0;
DS T1; T1.init();
for (int i = 0; i < h; i++){
p2[i] = (!i) ? make_pair(0, 0) : p2[i - 1];
h2[i] = (!i) ? 0 : h2[i - 1];
while (j < n && all[j].ss < imp[i]){
T1.add(all[j].ff);
T1.add(all[j].ss);
p2[i].ff++;
p2[i].ss += (all[j].ff + all[j].ss);
h2[i] += (all[j].ss - all[j].ff);
j++;
}
out1[i] = T1.get();
}
sort(all.begin(), all.end());
j = n - 1;
DS T2; T2.init();
for (int i = h - 1; i >= 0; i--){
p1[i] = (i == (h - 1)) ? make_pair(0, 0) : p1[i + 1];
h1[i] = (i == (h - 1)) ? 0 : h1[i + 1];
while (j >= 0 && all[j].ff > imp[i]){
T2.add(all[j].ff);
T2.add(all[j].ss);
p1[i].ff++;
p1[i].ss += (all[j].ff + all[j].ss);
h1[i] += (all[j].ss - all[j].ff);
j--;
}
out2[i] = T2.get();
}
for (int j = 0; j < h; j++){
int i = imp[j];
ll sum = S - h1[j] - h2[j];
ll s1 = out1[j] + p1[j].ss - 2LL * i * p1[j].ff;
ll s2 = out2[j] + 2LL * i * p2[j].ff - p2[j].ss;
mn = min(mn, sum + s1 + n);
mn = min(mn, sum + s2 + n);
}
}
if (mn == inf) mn = 0;
cout<<out + mn<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
