#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
const int MAX_N = 100000;
const long long INF = (1LL<<30) * MAX_N;
struct Range {
int l, r, color;
Range(int _l, int _r, int _color):l(_l), r(_r), color(_color) {}
};
vector<pair<int, int> > node;
vector<Range> ranges;
long long _dp[1+2*MAX_N], *dp = _dp + 1;
long long _sum[1+2*MAX_N], *sum = _sum + 1;
void initAll(int n) {
for(int i = -1; i < n; ++i)
dp[i] = sum[i] = 0;
ranges.clear();
node.clear();
}
void pushRange(int poz, int color, int x) {
if(ranges.back().color == color)
ranges.back().r = poz;
else
ranges.push_back(Range(poz, poz, color));
node.push_back(make_pair(x, color));
}
void mergeNodes(const vector<int> &r, const vector<int> &b) {
int i, j;
i = j = 0;
if(r[0] < b[0])
ranges.push_back({0, 0, 1});
else
ranges.push_back({0, 0, 2});
while(i < r.size() || j < b.size()) {
if(j == b.size() || (j < b.size() && i < r.size() && r[i] < b[j])) {
pushRange(i + j, 1, r[i]);
++i;
} else {
pushRange(i + j, 2, b[j]);
++j;
}
}
for(int i = 0; i < node.size(); ++i)
sum[i] = sum[i - 1] + node[i].first;
}
long long sumRange(int a, int b) {
return sum[b] - sum[a - 1];
}
void initDp() {
dp[-1] = 0;
for(int i = ranges[0].l; i <= ranges[0].r; ++i)
dp[i] = INF;
}
void doDp(int i) {
int l, r;
long long rgang = INF, lazy = 0LL, xdp = dp[ranges[i - 1].r];
priority_queue<pair<long long, int>,
vector<pair<long long, int> >,
std::greater<pair<long long, int> > > lgang;
l = ranges[i - 1].r;
r = ranges[i].l;
for(int j = ranges[i - 1].l; j <= ranges[i - 1].r; ++j)
lgang.push(make_pair(dp[j - 1] - sumRange(j, ranges[i - 1].r) + (long long)(ranges[i - 1].r - j + 1) * node[ranges[i].l].first, j));
while(r <= ranges[i].r) {
if(l >= ranges[i - 1].l) {
xdp = min(xdp, dp[l - 1]);
rgang = min(xdp - sumRange(l, ranges[i - 1].r), rgang - node[ranges[i - 1].r].first);
} else
rgang -= node[ranges[i - 1].r].first;
lazy -= node[ranges[i].l].first;
while(!lgang.empty() && ranges[i - 1].r - lgang.top().second <= r - ranges[i].l)
lgang.pop();
dp[r] = rgang + sumRange(ranges[i].l, r);
if(!lgang.empty())
dp[r] = min(dp[r], lgang.top().first + sumRange(ranges[i].l, r) + lazy);
--l;
++r;
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
initAll(r.size() + b.size());
mergeNodes(r, b);
initDp();
for(int i = 1; i < ranges.size(); ++i)
doDp(i);
return dp[node.size() - 1];
}
Compilation message
wiring.cpp: In function 'void mergeNodes(const std::vector<int>&, const std::vector<int>&)':
wiring.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < r.size() || j < b.size()) {
~~^~~~~~~~~~
wiring.cpp:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < r.size() || j < b.size()) {
~~^~~~~~~~~~
wiring.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j == b.size() || (j < b.size() && i < r.size() && r[i] < b[j])) {
~~^~~~~~~~~~~
wiring.cpp:44:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j == b.size() || (j < b.size() && i < r.size() && r[i] < b[j])) {
~~^~~~~~~~~~
wiring.cpp:44:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j == b.size() || (j < b.size() && i < r.size() && r[i] < b[j])) {
~~^~~~~~~~~~
wiring.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < node.size(); ++i)
~~^~~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < ranges.size(); ++i)
~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
504 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
36 ms |
8428 KB |
Output is correct |
4 |
Correct |
34 ms |
8424 KB |
Output is correct |
5 |
Correct |
36 ms |
7016 KB |
Output is correct |
6 |
Correct |
50 ms |
9960 KB |
Output is correct |
7 |
Correct |
43 ms |
9964 KB |
Output is correct |
8 |
Correct |
51 ms |
9960 KB |
Output is correct |
9 |
Correct |
52 ms |
9960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
52 ms |
7944 KB |
Output is correct |
4 |
Correct |
50 ms |
9328 KB |
Output is correct |
5 |
Correct |
2 ms |
252 KB |
Output is correct |
6 |
Correct |
1 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
52 ms |
9636 KB |
Output is correct |
19 |
Correct |
53 ms |
9636 KB |
Output is correct |
20 |
Correct |
55 ms |
9840 KB |
Output is correct |
21 |
Correct |
53 ms |
9640 KB |
Output is correct |
22 |
Correct |
53 ms |
9636 KB |
Output is correct |
23 |
Correct |
52 ms |
9640 KB |
Output is correct |
24 |
Correct |
53 ms |
10224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
43 ms |
7532 KB |
Output is correct |
3 |
Correct |
42 ms |
7788 KB |
Output is correct |
4 |
Correct |
41 ms |
7660 KB |
Output is correct |
5 |
Correct |
44 ms |
7788 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
47 ms |
9600 KB |
Output is correct |
19 |
Correct |
46 ms |
8460 KB |
Output is correct |
20 |
Correct |
45 ms |
8556 KB |
Output is correct |
21 |
Correct |
46 ms |
8680 KB |
Output is correct |
22 |
Correct |
44 ms |
11144 KB |
Output is correct |
23 |
Correct |
40 ms |
10984 KB |
Output is correct |
24 |
Correct |
45 ms |
11020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
504 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
36 ms |
8428 KB |
Output is correct |
20 |
Correct |
34 ms |
8424 KB |
Output is correct |
21 |
Correct |
36 ms |
7016 KB |
Output is correct |
22 |
Correct |
50 ms |
9960 KB |
Output is correct |
23 |
Correct |
43 ms |
9964 KB |
Output is correct |
24 |
Correct |
51 ms |
9960 KB |
Output is correct |
25 |
Correct |
52 ms |
9960 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
52 ms |
7944 KB |
Output is correct |
29 |
Correct |
50 ms |
9328 KB |
Output is correct |
30 |
Correct |
2 ms |
252 KB |
Output is correct |
31 |
Correct |
1 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
256 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
256 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
2 ms |
376 KB |
Output is correct |
39 |
Correct |
2 ms |
504 KB |
Output is correct |
40 |
Correct |
2 ms |
376 KB |
Output is correct |
41 |
Correct |
2 ms |
376 KB |
Output is correct |
42 |
Correct |
2 ms |
376 KB |
Output is correct |
43 |
Correct |
52 ms |
9636 KB |
Output is correct |
44 |
Correct |
53 ms |
9636 KB |
Output is correct |
45 |
Correct |
55 ms |
9840 KB |
Output is correct |
46 |
Correct |
53 ms |
9640 KB |
Output is correct |
47 |
Correct |
53 ms |
9636 KB |
Output is correct |
48 |
Correct |
52 ms |
9640 KB |
Output is correct |
49 |
Correct |
53 ms |
10224 KB |
Output is correct |
50 |
Correct |
1 ms |
256 KB |
Output is correct |
51 |
Correct |
43 ms |
7532 KB |
Output is correct |
52 |
Correct |
42 ms |
7788 KB |
Output is correct |
53 |
Correct |
41 ms |
7660 KB |
Output is correct |
54 |
Correct |
44 ms |
7788 KB |
Output is correct |
55 |
Correct |
2 ms |
376 KB |
Output is correct |
56 |
Correct |
2 ms |
376 KB |
Output is correct |
57 |
Correct |
2 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |
59 |
Correct |
2 ms |
376 KB |
Output is correct |
60 |
Correct |
2 ms |
376 KB |
Output is correct |
61 |
Correct |
2 ms |
376 KB |
Output is correct |
62 |
Correct |
2 ms |
376 KB |
Output is correct |
63 |
Correct |
2 ms |
376 KB |
Output is correct |
64 |
Correct |
2 ms |
376 KB |
Output is correct |
65 |
Correct |
2 ms |
376 KB |
Output is correct |
66 |
Correct |
2 ms |
376 KB |
Output is correct |
67 |
Correct |
47 ms |
9600 KB |
Output is correct |
68 |
Correct |
46 ms |
8460 KB |
Output is correct |
69 |
Correct |
45 ms |
8556 KB |
Output is correct |
70 |
Correct |
46 ms |
8680 KB |
Output is correct |
71 |
Correct |
44 ms |
11144 KB |
Output is correct |
72 |
Correct |
40 ms |
10984 KB |
Output is correct |
73 |
Correct |
45 ms |
11020 KB |
Output is correct |
74 |
Correct |
51 ms |
11812 KB |
Output is correct |
75 |
Correct |
44 ms |
10024 KB |
Output is correct |
76 |
Correct |
53 ms |
11668 KB |
Output is correct |
77 |
Correct |
51 ms |
10060 KB |
Output is correct |
78 |
Correct |
49 ms |
11128 KB |
Output is correct |
79 |
Correct |
44 ms |
9960 KB |
Output is correct |
80 |
Correct |
44 ms |
10984 KB |
Output is correct |
81 |
Correct |
46 ms |
11492 KB |
Output is correct |
82 |
Correct |
44 ms |
11104 KB |
Output is correct |
83 |
Correct |
44 ms |
11292 KB |
Output is correct |
84 |
Correct |
47 ms |
11628 KB |
Output is correct |
85 |
Correct |
51 ms |
10344 KB |
Output is correct |
86 |
Correct |
57 ms |
11712 KB |
Output is correct |
87 |
Correct |
49 ms |
11624 KB |
Output is correct |
88 |
Correct |
49 ms |
10472 KB |
Output is correct |
89 |
Correct |
52 ms |
10500 KB |
Output is correct |
90 |
Correct |
58 ms |
10524 KB |
Output is correct |
91 |
Correct |
49 ms |
11756 KB |
Output is correct |
92 |
Correct |
53 ms |
11660 KB |
Output is correct |
93 |
Correct |
50 ms |
11636 KB |
Output is correct |
94 |
Correct |
53 ms |
11588 KB |
Output is correct |
95 |
Correct |
55 ms |
10424 KB |
Output is correct |
96 |
Correct |
50 ms |
11624 KB |
Output is correct |
97 |
Correct |
56 ms |
12208 KB |
Output is correct |
98 |
Correct |
52 ms |
11608 KB |
Output is correct |
99 |
Correct |
53 ms |
11640 KB |
Output is correct |
100 |
Correct |
57 ms |
11648 KB |
Output is correct |
101 |
Correct |
51 ms |
11968 KB |
Output is correct |
102 |
Correct |
50 ms |
11624 KB |
Output is correct |