#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define maxc 1000000007
using namespace std;
int k, n, rr[2*N];
pii a[N];
long long f[2][N];
struct IntervalTree
{
long long t[N << 3];
int sz[N << 3];
void build(int l, int r, int id)
{
t[id] = sz[id] = 0;
if (l == r) return;
int mid = (r + l)/2;
build(l, mid, id*2);
build(mid+1, r, id*2+1);
}
void update(int l, int r, int id, int x, int val)
{
if (l == r)
{
t[id] += val;
sz[id]++;
return;
}
int mid = (r + l)/2;
if (x <= mid) update(l, mid, id*2, x, val);
else update(mid+1, r, id*2+1, x, val);
t[id] += val;
sz[id]++;
}
int getpos(int l, int r, int id, int x)
{
if (l == r) return l;
int mid = (r + l)/2;
if (sz[id*2] >= x) return getpos(l, mid, id*2, x);
return getpos(mid+1, r, id*2+1, x-sz[id*2]);
}
long long get(int l, int r, int id, int x, int y)
{
if (l > y || r < x) return 0;
if (l >= x && r <= y) return t[id];
int mid = (r + l)/2;
long long a = get(l, mid, id*2, x, y);
long long b = get(mid+1, r, id*2+1, x, y);
return a + b;
}
int getSz(int l, int r, int id, int x, int y)
{
if (l > y || r < x) return 0;
if (l >= x && r <= y) return sz[id];
int mid = (r + l)/2;
int a = getSz(l, mid, id*2, x, y);
int b = getSz(mid+1, r, id*2+1, x, y);
return a + b;
}
}t;
bool cmp(pii x, pii y)
{
return x.F + x.S < y.F + y.S;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
cin >> k >> n;
int cur = 0;
long long ans = 0;
for (int i = 1; i <= n; i++)
{
char x, y; int u, v;
cin >> x >> u >> y >> v;
if (x == y) ans += abs(u-v);
else {
if (u > v) swap(u, v);
a[++cur] = mp(u, v);
}
}
n = cur;
sort(a+1, a+n+1, cmp);
cur = 0;
for (int i = 1; i <= n; i++)
{
rr[++cur] = a[i].F;
rr[++cur] = a[i].S;
}
sort(rr+1, rr+cur+1);
cur = unique(rr+1, rr+cur+1) - rr - 1;
for (int i = 1; i <= n; i++)
{
a[i].F = lower_bound(rr+1, rr+cur+1, a[i].F) - rr;
a[i].S = lower_bound(rr+1, rr+cur+1, a[i].S) - rr;
}
for (int i = 1; i <= n; i++)
{
t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);
int pos = t.getpos(1, 2*n, 1, i);
long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
f[0][i] = xx + yy;
}
t.build(1, 2*n, 1);
for (int i = n; i >= 1; i--)
{
t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);
int pos = t.getpos(1, 2*n, 1, i);
long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
f[1][i] = xx + yy;
}
if (k == 1) cout <<f[0][n] + ans + n;
else
{
long long res = maxc;
for (int i = 0; i <= n; i++)
res = min(res, ans + f[0][i] + f[1][i+1] + n);
cout <<res;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
