/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200002;
const ll INF = LLONG_MAX / 2;
struct Node
{
ll x;
bool color;
};
bool operator < (const Node &a, const Node &b)
{
return a.x < b.x;
}
int n;
Node v[N_MAX];
int prevL[N_MAX], prevR[N_MAX];
int L[N_MAX], R[N_MAX];
ll sumPref[N_MAX];
ll dp[N_MAX];
ll SGT1[N_MAX * 4], SGT2[N_MAX * 4];
void build (ll SGT[], int node, int l, int r)
{
if(l == r)
{
SGT[node] = INF;
return;
}
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
build(SGT, lSon, l, mid);
build(SGT, rSon, mid + 1, r);
SGT[node] = min(SGT[lSon], SGT[rSon]);
}
void update (ll SGT[], int node, int l, int r, int upos, ll uval)
{
if(l == r)
{
SGT[node] = uval;
return;
}
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
if(upos <= mid)
update(SGT, lSon, l, mid, upos, uval);
else
update(SGT, rSon, mid + 1, r, upos, uval);
SGT[node] = min(SGT[lSon], SGT[rSon]);
}
ll query (ll SGT[], int node, int l, int r, int ql, int qr)
{
if(ql > qr)
return INF;
if(ql <= l && r <= qr)
return SGT[node];
int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
if(ql <= mid && mid + 1 <= qr)
return min(query(SGT, lSon, l, mid, ql, qr), query(SGT, rSon, mid + 1, r, ql, qr));
else if(ql <= mid)
return query(SGT, lSon, l, mid, ql, qr);
else
return query(SGT, rSon, mid + 1, r, ql, qr);
}
ll min_total_length (vector <int> rv, vector <int> bv)
{
for(int x : rv)
v[++n] = Node{x, 0};
for(int x : bv)
v[++n] = Node{x, 1};
sort(v + 1, v + n + 1);
int currL = 1, currR = 0;
v[n + 1].color = !v[n].color;
for(int i = 1; i <= n + 1; i++)
{
if(i > 1 && v[i].color != v[i - 1].color)
{
for(int j = i - 1; j >= 1 && v[j].color == v[i - 1].color; j--)
{
L[j] = currL;
R[j] = currR;
}
prevL[i] = currL;
prevR[i] = currR;
currL = i;
}
else
{
prevL[i] = prevL[i - 1];
prevR[i] = prevR[i - 1];
}
currR = i;
}
for(int i = 1; i <= n; i++)
sumPref[i] = sumPref[i - 1] + v[i].x;
build(SGT1, 1, 1, n);
build(SGT2, 1, 1, n);
update(SGT1, 1, 1, n, 1, - v[R[1] + 1].x);
update(SGT2, 1, 1, n, 1, - v[R[1]].x);
for(int i = 1; i <= n; i++)
{
if(prevL[i] == 0)
dp[i] = INF;
else
{
int k = prevR[i];
int l1 = prevL[i], r1 = min(prevR[i], 2 * k - i);
int l2 = max(prevL[i], 2 * k - i + 1), r2 = prevR[i];
dp[i] = min({INF,
query(SGT1, 1, 1, n, l1, r1) + sumPref[i] - 2 * sumPref[k] + v[k + 1].x * (2 * k - i + 1),
query(SGT2, 1, 1, n, l2, r2) + sumPref[i] - 2 * sumPref[k] - v[k].x * (i - 2 * k - 1)});
update(SGT1, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i] + 1].x * i);
update(SGT2, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i]].x * i);
}
}
return dp[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
66 ms |
16876 KB |
Output is correct |
4 |
Correct |
64 ms |
16748 KB |
Output is correct |
5 |
Correct |
82 ms |
16748 KB |
Output is correct |
6 |
Correct |
111 ms |
19464 KB |
Output is correct |
7 |
Correct |
107 ms |
19436 KB |
Output is correct |
8 |
Correct |
98 ms |
19436 KB |
Output is correct |
9 |
Correct |
105 ms |
19532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
150 ms |
19592 KB |
Output is correct |
4 |
Correct |
154 ms |
21100 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
147 ms |
21484 KB |
Output is correct |
19 |
Correct |
148 ms |
21356 KB |
Output is correct |
20 |
Correct |
160 ms |
21484 KB |
Output is correct |
21 |
Correct |
148 ms |
21368 KB |
Output is correct |
22 |
Correct |
149 ms |
21484 KB |
Output is correct |
23 |
Correct |
164 ms |
21496 KB |
Output is correct |
24 |
Correct |
150 ms |
21484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
163 ms |
19564 KB |
Output is correct |
3 |
Correct |
146 ms |
19436 KB |
Output is correct |
4 |
Correct |
161 ms |
19436 KB |
Output is correct |
5 |
Correct |
149 ms |
19564 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
180 ms |
20792 KB |
Output is correct |
19 |
Correct |
164 ms |
20716 KB |
Output is correct |
20 |
Correct |
162 ms |
20716 KB |
Output is correct |
21 |
Correct |
164 ms |
20716 KB |
Output is correct |
22 |
Correct |
136 ms |
20716 KB |
Output is correct |
23 |
Correct |
111 ms |
20716 KB |
Output is correct |
24 |
Correct |
131 ms |
20716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
66 ms |
16876 KB |
Output is correct |
20 |
Correct |
64 ms |
16748 KB |
Output is correct |
21 |
Correct |
82 ms |
16748 KB |
Output is correct |
22 |
Correct |
111 ms |
19464 KB |
Output is correct |
23 |
Correct |
107 ms |
19436 KB |
Output is correct |
24 |
Correct |
98 ms |
19436 KB |
Output is correct |
25 |
Correct |
105 ms |
19532 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
150 ms |
19592 KB |
Output is correct |
29 |
Correct |
154 ms |
21100 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
1 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
1 ms |
364 KB |
Output is correct |
43 |
Correct |
147 ms |
21484 KB |
Output is correct |
44 |
Correct |
148 ms |
21356 KB |
Output is correct |
45 |
Correct |
160 ms |
21484 KB |
Output is correct |
46 |
Correct |
148 ms |
21368 KB |
Output is correct |
47 |
Correct |
149 ms |
21484 KB |
Output is correct |
48 |
Correct |
164 ms |
21496 KB |
Output is correct |
49 |
Correct |
150 ms |
21484 KB |
Output is correct |
50 |
Correct |
1 ms |
364 KB |
Output is correct |
51 |
Correct |
163 ms |
19564 KB |
Output is correct |
52 |
Correct |
146 ms |
19436 KB |
Output is correct |
53 |
Correct |
161 ms |
19436 KB |
Output is correct |
54 |
Correct |
149 ms |
19564 KB |
Output is correct |
55 |
Correct |
1 ms |
364 KB |
Output is correct |
56 |
Correct |
1 ms |
364 KB |
Output is correct |
57 |
Correct |
1 ms |
364 KB |
Output is correct |
58 |
Correct |
1 ms |
364 KB |
Output is correct |
59 |
Correct |
1 ms |
364 KB |
Output is correct |
60 |
Correct |
1 ms |
364 KB |
Output is correct |
61 |
Correct |
1 ms |
364 KB |
Output is correct |
62 |
Correct |
1 ms |
364 KB |
Output is correct |
63 |
Correct |
1 ms |
364 KB |
Output is correct |
64 |
Correct |
1 ms |
364 KB |
Output is correct |
65 |
Correct |
1 ms |
364 KB |
Output is correct |
66 |
Correct |
1 ms |
364 KB |
Output is correct |
67 |
Correct |
180 ms |
20792 KB |
Output is correct |
68 |
Correct |
164 ms |
20716 KB |
Output is correct |
69 |
Correct |
162 ms |
20716 KB |
Output is correct |
70 |
Correct |
164 ms |
20716 KB |
Output is correct |
71 |
Correct |
136 ms |
20716 KB |
Output is correct |
72 |
Correct |
111 ms |
20716 KB |
Output is correct |
73 |
Correct |
131 ms |
20716 KB |
Output is correct |
74 |
Correct |
116 ms |
21612 KB |
Output is correct |
75 |
Correct |
136 ms |
21100 KB |
Output is correct |
76 |
Correct |
131 ms |
21612 KB |
Output is correct |
77 |
Correct |
163 ms |
20844 KB |
Output is correct |
78 |
Correct |
142 ms |
21100 KB |
Output is correct |
79 |
Correct |
157 ms |
20844 KB |
Output is correct |
80 |
Correct |
123 ms |
20844 KB |
Output is correct |
81 |
Correct |
109 ms |
20972 KB |
Output is correct |
82 |
Correct |
101 ms |
21156 KB |
Output is correct |
83 |
Correct |
108 ms |
21100 KB |
Output is correct |
84 |
Correct |
102 ms |
21484 KB |
Output is correct |
85 |
Correct |
149 ms |
21416 KB |
Output is correct |
86 |
Correct |
132 ms |
21484 KB |
Output is correct |
87 |
Correct |
127 ms |
21484 KB |
Output is correct |
88 |
Correct |
140 ms |
21484 KB |
Output is correct |
89 |
Correct |
132 ms |
21484 KB |
Output is correct |
90 |
Correct |
162 ms |
21496 KB |
Output is correct |
91 |
Correct |
117 ms |
21484 KB |
Output is correct |
92 |
Correct |
150 ms |
21484 KB |
Output is correct |
93 |
Correct |
132 ms |
21484 KB |
Output is correct |
94 |
Correct |
154 ms |
21484 KB |
Output is correct |
95 |
Correct |
161 ms |
21484 KB |
Output is correct |
96 |
Correct |
119 ms |
21476 KB |
Output is correct |
97 |
Correct |
120 ms |
21484 KB |
Output is correct |
98 |
Correct |
139 ms |
21484 KB |
Output is correct |
99 |
Correct |
132 ms |
21612 KB |
Output is correct |
100 |
Correct |
162 ms |
21484 KB |
Output is correct |
101 |
Correct |
121 ms |
21484 KB |
Output is correct |
102 |
Correct |
130 ms |
21484 KB |
Output is correct |