#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 1000000000000000007ll
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);
//freopen("BRIDGE.INP", "r", stdin);
//freopen("BRIDGE.OUT", "w", stdout);
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;
if (n == 0)
{
cout <<ans;
return 0;
}
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, (n-i+1));
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 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
540 KB |
Output is correct |
4 |
Correct |
5 ms |
624 KB |
Output is correct |
5 |
Correct |
4 ms |
736 KB |
Output is correct |
6 |
Correct |
3 ms |
776 KB |
Output is correct |
7 |
Correct |
4 ms |
796 KB |
Output is correct |
8 |
Correct |
3 ms |
820 KB |
Output is correct |
9 |
Correct |
4 ms |
840 KB |
Output is correct |
10 |
Correct |
4 ms |
972 KB |
Output is correct |
11 |
Correct |
4 ms |
972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
972 KB |
Output is correct |
2 |
Correct |
2 ms |
972 KB |
Output is correct |
3 |
Correct |
3 ms |
984 KB |
Output is correct |
4 |
Correct |
4 ms |
992 KB |
Output is correct |
5 |
Correct |
4 ms |
1012 KB |
Output is correct |
6 |
Correct |
3 ms |
1012 KB |
Output is correct |
7 |
Correct |
4 ms |
1076 KB |
Output is correct |
8 |
Correct |
3 ms |
1100 KB |
Output is correct |
9 |
Correct |
5 ms |
1120 KB |
Output is correct |
10 |
Correct |
3 ms |
1144 KB |
Output is correct |
11 |
Correct |
4 ms |
1164 KB |
Output is correct |
12 |
Correct |
153 ms |
11108 KB |
Output is correct |
13 |
Correct |
334 ms |
13476 KB |
Output is correct |
14 |
Correct |
204 ms |
14408 KB |
Output is correct |
15 |
Correct |
222 ms |
14408 KB |
Output is correct |
16 |
Correct |
143 ms |
17612 KB |
Output is correct |
17 |
Correct |
261 ms |
19956 KB |
Output is correct |
18 |
Correct |
169 ms |
21960 KB |
Output is correct |
19 |
Correct |
282 ms |
24292 KB |
Output is correct |
20 |
Correct |
170 ms |
26168 KB |
Output is correct |
21 |
Correct |
248 ms |
28316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
28316 KB |
Output is correct |
2 |
Correct |
2 ms |
28316 KB |
Output is correct |
3 |
Correct |
2 ms |
28316 KB |
Output is correct |
4 |
Correct |
2 ms |
28316 KB |
Output is correct |
5 |
Correct |
2 ms |
28316 KB |
Output is correct |
6 |
Correct |
2 ms |
28316 KB |
Output is correct |
7 |
Correct |
2 ms |
28316 KB |
Output is correct |
8 |
Correct |
2 ms |
28316 KB |
Output is correct |
9 |
Correct |
2 ms |
28316 KB |
Output is correct |
10 |
Correct |
2 ms |
28316 KB |
Output is correct |
11 |
Correct |
2 ms |
28316 KB |
Output is correct |
12 |
Correct |
2 ms |
28316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
28316 KB |
Output is correct |
2 |
Correct |
2 ms |
28316 KB |
Output is correct |
3 |
Correct |
2 ms |
28316 KB |
Output is correct |
4 |
Correct |
2 ms |
28316 KB |
Output is correct |
5 |
Correct |
2 ms |
28316 KB |
Output is correct |
6 |
Correct |
2 ms |
28316 KB |
Output is correct |
7 |
Correct |
2 ms |
28316 KB |
Output is correct |
8 |
Correct |
2 ms |
28316 KB |
Output is correct |
9 |
Correct |
2 ms |
28316 KB |
Output is correct |
10 |
Correct |
2 ms |
28316 KB |
Output is correct |
11 |
Correct |
2 ms |
28316 KB |
Output is correct |
12 |
Correct |
2 ms |
28316 KB |
Output is correct |
13 |
Correct |
3 ms |
28316 KB |
Output is correct |
14 |
Correct |
3 ms |
28316 KB |
Output is correct |
15 |
Correct |
5 ms |
28316 KB |
Output is correct |
16 |
Correct |
3 ms |
28316 KB |
Output is correct |
17 |
Correct |
3 ms |
28316 KB |
Output is correct |
18 |
Correct |
2 ms |
28316 KB |
Output is correct |
19 |
Correct |
3 ms |
28316 KB |
Output is correct |
20 |
Correct |
5 ms |
28316 KB |
Output is correct |
21 |
Correct |
4 ms |
28316 KB |
Output is correct |
22 |
Correct |
4 ms |
28316 KB |
Output is correct |
23 |
Correct |
4 ms |
28316 KB |
Output is correct |
24 |
Correct |
4 ms |
28316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
28316 KB |
Output is correct |
2 |
Correct |
2 ms |
28316 KB |
Output is correct |
3 |
Correct |
2 ms |
28316 KB |
Output is correct |
4 |
Correct |
2 ms |
28316 KB |
Output is correct |
5 |
Correct |
2 ms |
28316 KB |
Output is correct |
6 |
Correct |
2 ms |
28316 KB |
Output is correct |
7 |
Correct |
2 ms |
28316 KB |
Output is correct |
8 |
Correct |
2 ms |
28316 KB |
Output is correct |
9 |
Correct |
2 ms |
28316 KB |
Output is correct |
10 |
Correct |
2 ms |
28316 KB |
Output is correct |
11 |
Correct |
2 ms |
28316 KB |
Output is correct |
12 |
Correct |
2 ms |
28316 KB |
Output is correct |
13 |
Correct |
3 ms |
28316 KB |
Output is correct |
14 |
Correct |
3 ms |
28316 KB |
Output is correct |
15 |
Correct |
4 ms |
28316 KB |
Output is correct |
16 |
Correct |
2 ms |
28316 KB |
Output is correct |
17 |
Correct |
3 ms |
28316 KB |
Output is correct |
18 |
Correct |
3 ms |
28316 KB |
Output is correct |
19 |
Correct |
3 ms |
28316 KB |
Output is correct |
20 |
Correct |
4 ms |
28316 KB |
Output is correct |
21 |
Correct |
3 ms |
28316 KB |
Output is correct |
22 |
Correct |
4 ms |
28316 KB |
Output is correct |
23 |
Correct |
3 ms |
28316 KB |
Output is correct |
24 |
Correct |
4 ms |
28316 KB |
Output is correct |
25 |
Correct |
151 ms |
29556 KB |
Output is correct |
26 |
Correct |
179 ms |
30596 KB |
Output is correct |
27 |
Correct |
347 ms |
32324 KB |
Output is correct |
28 |
Correct |
341 ms |
34736 KB |
Output is correct |
29 |
Correct |
350 ms |
37112 KB |
Output is correct |
30 |
Correct |
158 ms |
37112 KB |
Output is correct |
31 |
Correct |
138 ms |
39848 KB |
Output is correct |
32 |
Correct |
260 ms |
42296 KB |
Output is correct |
33 |
Correct |
188 ms |
44108 KB |
Output is correct |
34 |
Correct |
273 ms |
46440 KB |
Output is correct |
35 |
Correct |
197 ms |
48416 KB |
Output is correct |
36 |
Correct |
275 ms |
50508 KB |
Output is correct |
37 |
Correct |
141 ms |
51216 KB |
Output is correct |