#include <bits/stdc++.h>
#define ll long long
using namespace std;
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif // BALBIT
//#define int ll
#define pii pair<ll, ll>
#define f first
#define s second
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define pb push_back
vector<pii> v;
int n;
const int maxn = 1e5+3;
vector<int> rbs, lbs;// right bounds and left bounds, separated and sorted
ll rps[maxn], lps[maxn];// right bounds and left bounds, separated and sorted and ps
struct node{
node *lc=0, *rc=0;
ll val=0;
int sz=0;
} pool [10000000];
auto _ptr = pool;
inline ll getval(node *&o){return o?o->val:0;}
inline int getsz(node *&o){return o?o->sz:0;}
node* MO(node *o, ll l, ll r, ll p, int v) {
// if (!o) o = new node();
node * ret = new (_ptr++)node ();
if (o) ret->lc = o->lc, ret->rc = o->rc, ret->val = o->val, ret->sz = o->sz;
// ret -> val = o->val; ret->sz = o->sz;
if (l == r) {
bug(p);
ret->val += v;
ret->sz += 1;
// if (ret->val == 20) bug(ret->val, ret->sz);
return ret;
}
// if (!o->lc) o->lc = new node();
// if (!o->rc) o->rc = new node();
ll mid = (l+r)/2;
if (p <= mid) {
ret -> lc = MO(ret->lc, l, mid, p, v);
// ret -> rc = o->rc;
}
else{
// ret -> lc = o->lc;
ret -> rc = MO(ret->rc, mid+1, r, p, v);
}
ret->val = getval(ret->lc) + getval(ret->rc);
ret->sz = getsz(ret->lc) + getsz(ret->rc);
// if (ret->val == 20) bug(ret->val, ret->sz);
return ret;
}
pii QU(node *&o, ll l, ll r, int L, int R) {
if (!o || l > R || r<L) return {0,0};
if (l>=L && r <=R) return {o->val, o->sz};
ll mid = (l+r)/2;
pii A = QU(o->lc, l,mid, L, R);
pii B = QU(o->rc,mid+1,r, L, R);
return {A.f+B.f, A.s+B.s};
}
//void MOO(node *o, int l, int r, int p, int v) {
// if (o == nullptr) o = new node();
// if (l == r) {
// o->val = p;
// return;
// }
// int mid = (l+r)/2;
// if (p <= mid) {
// o -> lc = MO(o->lc, l, mid, p, v);
// }
// else{
// o -> rc = MO(o->rc, mid+1, r, p, v);
// }
// o->val = getval(o->lc) + getval(o->rc);
// o->sz = getsz(o->lc) + getsz(o->rc);
//}
vector<node*> lhistory, rhistory;
vector<int> lrev;
map<ll, int> segmp;
ll C(ll l, ll r) {
if (l>r) swap(l,r);
int L = lower_bound(ALL(rbs), l) - rbs.begin() -1;// right bounds less than l
int R = upper_bound(ALL(lbs), r) - lbs.begin();// right bounds less than l
ll re = 0;
re += (lps[n] - lps[R]) - (n-R) * r;
bug(re);
bug(L+1);
re += (L+1) * (l) - (rps[L+1]);
bug(re);
int lat = lower_bound(ALL(lrev), l, greater<int>()) - lrev.begin() - 1;
int rat = lower_bound(ALL(rbs), r) - rbs.begin()-1;
bug(lat, rat);
pii lq = QU(lhistory[lat+1], 0, 1e5+3, 0, (*prev(segmp.lower_bound(r+l))).s);
pii rq = QU(rhistory[rat+1], 0, 1e5+3, (*(segmp.lower_bound(r+l))).s, 1e5+3);
bug(lq.f, lq.s, rq.f, rq.s);
re += lq.f - lq.s * l;
re += rq.s * r - rq.f;
return re;
}
ll RE;
vector<int> p;
int m;
node * lroot = 0, *rroot = 0;
void go(int il, int ir, int jl, int jr) {
if (il > ir || jl > jr) return;
int mid = (il + ir)/2;
int best = -1;
ll bestval = 2e18+3;
for (int j = jl; j<=min(mid, p[j]); ++j) {
ll tt = C(p[mid], p[j]);
RE = min (RE, tt);
if (tt < bestval) {
best = j; bestval = tt;
}
}
go(il, mid-1, jl, best);
go(mid+1, ir, best, jr);
}
signed main(){
IOS();
int k; cin>>k>>n;
ll re = 0;
map<int, int> hv;
for (int i = 0; i<n; ++i) {
char x, x2;
int l, r; cin>>x>>l>>x2>>r;
re += abs(r-l);
if (x == x2) {
}else{
if (r < l) swap(l,r);
v.pb({l,r});
rbs.pb(r);
lbs.pb(l);
hv[l]--;
hv[r]--;
}
}
n = SZ(v);
lhistory.pb(nullptr);
rhistory.pb(nullptr);
sort(ALL(v), [&](pii a, pii b){return a.f>b.f;});
vector<ll> fff;
for (int i = 0; i<n; ++i) {
fff.pb(v[i].f + v[i].s);
}
sort(ALL(fff));
for (int i = 0; i<n; ++i) {
segmp[fff[i]] = i;
}
segmp[-1]=-1;
for (int i = 0; i<n; ++i) {
lhistory.pb(MO(lhistory.back(), 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].f));
}
sort(ALL(v), [&](pii a, pii b){return a.s<b.s;});
for (int i = 0; i<n; ++i) {
// if (v[i].s == 6) bug(v[i].s, v[i].f+v[i].s);
rhistory.pb(MO(rhistory.back(), 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].s));
}
sort(ALL(rbs));
sort(ALL(lbs));
lrev = lbs;
sort(ALL(lrev), greater<int>());
for (int i = 0; i<n; ++i) {
rps[i+1] = rps[i] + rbs[i];
lps[i+1] = lps[i] + lbs[i];
}
// int L, R;
// while (cin>>L>>R) {
// cout<<C(L, R)<<endl;
// }
//
// return 0;
if (k == 1) {
ll now = lps[n];
bug(now);
ll ans = now;
ll x = 0;
ll frt = n;
for (pii ele : hv) {
ll X = ele.f;
now -= (X-x) * (frt);
bug(X, now);
ans = min(ans, now);
frt += ele.s;
x=X;
}
// if (ans == 1000000000000000ll) ans = 0;
cout<<re + ans*2 + n<<endl;
}else{
m = SZ(hv);
p.resize(m);
RE = C(0,0);
int _it = 0;
for (pii ele : hv) {
p[_it++] = ele.f;
}
go(0,m-1,0,m-1);
// cout<<re + ans*2 + n<<endl;
bug(RE);
cout<<re + RE*2 + n<<endl;
}
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
