#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
struct SegTree
{
vector<int> data;
vector<int> lazy;
int n;
SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
void push(int l, int r, int index)
{
data[index] += lazy[index];
if (data[index] > INF)
data[index] = INF;
if (r - l > 1)
{
lazy[index<<1] += lazy[index];
lazy[(index<<1)|1] += lazy[index];
}
lazy[index] = 0;
}
void updater(int l, int r, int index, int ss, int ee, int val)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] += val;
push(l, r, index);
return;
}
int m = l+r>>1;
updater(l, m, index<<1, ss, ee, val);
updater(m, r, (index<<1)|1, ss, ee, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
void updatep(int l, int r, int index, int i, int val)
{
push(l, r, index);
if (i >= r || l > i)
return;
if (r - l == 1)
{
data[index] = min(data[index], val);
return;
}
int m = l+r>>1;
updatep(l, m, index<<1, i, val);
updatep(m, r, (index<<1)|1, i, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
int query(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (l >= ee || ss >= r)
return INF;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
int lval = query(l, m, index<<1, ss, ee);
int rval = query(m, r, (index<<1)|1, ss, ee);
return min(lval, rval);
}
void clear() { lazy.clear(); data.clear(); }
void updater(int ss, int ee, int val) { updater(0, n, 1, ss, ee, val); }
void updatep(int i, int val) { updatep(0, n, 1, i, val); }
int query(int ss, int ee) { return query(0, n, 1, ss, ee); }
};
deque<int> r, b;
long long subtask2()
{
int m = r.back();
int sum = 0;
for (int i : r)
sum += m - i;
for (int i : b)
sum += i - m;
if (r.size() > b.size())
sum += (b[0] - m) * (r.size() - b.size());
return sum;
}
long long min_total_length(vector<int32_t> rr, vector<int32_t> bb)
{
for (int i : rr)
r.push_back(i);
for (int i : bb)
b.push_back(i);
if (r.back() < b[0])
return subtask2();
int g = 200;
if (rr.size() > 200 || bb.size() > 200)
g = 9;
int current = 0;
//fill(dp.begin(), dp.begin() + g, INF);
//dp[0] = 0;
if (r[0] > b[0])
swap(r, b);
int mnr = -INF;
SegTree st(1);
SegTree st2(1);
st.updatep(0, 0);
debug(r, b);
while (r.size() || b.size())
{
vector<int> v;
assert(v.size() < g);
while (r.size() && (b.empty() || r[0] < b[0]))
{
v.pb(r[0]);
r.pop_front();
}
st2.clear();
st2 = SegTree(v.size()+1);
int rb = b[0], lb = v[0];
int lsum = 0, rsum = 0;
for (int j = 0; j < v.size(); j++)
rsum += rb - v[j];
for (int i = v.size(); i >= 0; i--) // How many we're putting to right
{
//j for (int j = v.size()-i; j < v.size(); j++)
// rsum += rb - v[j];
debug(i, st.query(0, st.n), lsum, rsum);
st2.updatep(i, st.query(0, st.n) + lsum + rsum);
st.updater(0, v.size()-i+1, lb - mnr);
if (i > 0)
{
lsum += v[v.size()-i] - lb;
rsum -= rb- v[v.size()-i];
}
//for (int j = g-1; j >= 0; j--) // How many is coming from right
//{
// if (j < v.size()-i) // We need to take more
// dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
// else
// dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
// We might need to give more as well (but it has 0 contribution so it doesn't matter)
//}
}
mnr = v.back();
swap(r, b);
swap(st, st2);
debug(r, b);
}
return st.query(0, 1);
}
Compilation message
wiring.cpp: In constructor 'SegTree::SegTree(int64_t)':
wiring.cpp:27:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
27 | int n;
| ^
wiring.cpp:25:14: warning: 'std::vector<long int> SegTree::data' [-Wreorder]
25 | vector<int> data;
| ^~~~
wiring.cpp:28:2: warning: when initialized here [-Wreorder]
28 | SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
| ^~~~~~~
wiring.cpp: In member function 'void SegTree::updater(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int m = l+r>>1;
| ~^~
wiring.cpp: In member function 'void SegTree::updatep(int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int m = l+r>>1;
| ~^~
wiring.cpp: In member function 'int64_t SegTree::query(int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int m = l+r>>1;
| ~^~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from wiring.cpp:1:
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:131:19: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
131 | assert(v.size() < g);
| ~~~~~~~~~^~~
wiring.cpp:141:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int j = 0; j < v.size(); j++)
| ~~^~~~~~~~~~
wiring.cpp:118:6: warning: unused variable 'current' [-Wunused-variable]
118 | int current = 0;
| ^~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
13 ms |
4080 KB |
Output is correct |
4 |
Correct |
14 ms |
4084 KB |
Output is correct |
5 |
Correct |
13 ms |
4180 KB |
Output is correct |
6 |
Correct |
18 ms |
5432 KB |
Output is correct |
7 |
Correct |
32 ms |
5424 KB |
Output is correct |
8 |
Correct |
18 ms |
5432 KB |
Output is correct |
9 |
Correct |
25 ms |
5344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
38 ms |
5452 KB |
Output is correct |
4 |
Correct |
31 ms |
5096 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
33 ms |
5420 KB |
Output is correct |
19 |
Correct |
39 ms |
5412 KB |
Output is correct |
20 |
Correct |
36 ms |
5424 KB |
Output is correct |
21 |
Correct |
33 ms |
5428 KB |
Output is correct |
22 |
Correct |
34 ms |
5460 KB |
Output is correct |
23 |
Correct |
33 ms |
5428 KB |
Output is correct |
24 |
Correct |
34 ms |
5440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
304 KB |
Output is correct |
2 |
Correct |
63 ms |
6572 KB |
Output is correct |
3 |
Correct |
30 ms |
4692 KB |
Output is correct |
4 |
Correct |
50 ms |
4924 KB |
Output is correct |
5 |
Correct |
30 ms |
4796 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
85 ms |
12992 KB |
Output is correct |
19 |
Correct |
53 ms |
4812 KB |
Output is correct |
20 |
Correct |
57 ms |
5040 KB |
Output is correct |
21 |
Correct |
73 ms |
8040 KB |
Output is correct |
22 |
Correct |
86 ms |
16884 KB |
Output is correct |
23 |
Correct |
73 ms |
14700 KB |
Output is correct |
24 |
Correct |
92 ms |
16316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
13 ms |
4080 KB |
Output is correct |
20 |
Correct |
14 ms |
4084 KB |
Output is correct |
21 |
Correct |
13 ms |
4180 KB |
Output is correct |
22 |
Correct |
18 ms |
5432 KB |
Output is correct |
23 |
Correct |
32 ms |
5424 KB |
Output is correct |
24 |
Correct |
18 ms |
5432 KB |
Output is correct |
25 |
Correct |
25 ms |
5344 KB |
Output is correct |
26 |
Correct |
0 ms |
308 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
38 ms |
5452 KB |
Output is correct |
29 |
Correct |
31 ms |
5096 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
300 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
304 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
33 ms |
5420 KB |
Output is correct |
44 |
Correct |
39 ms |
5412 KB |
Output is correct |
45 |
Correct |
36 ms |
5424 KB |
Output is correct |
46 |
Correct |
33 ms |
5428 KB |
Output is correct |
47 |
Correct |
34 ms |
5460 KB |
Output is correct |
48 |
Correct |
33 ms |
5428 KB |
Output is correct |
49 |
Correct |
34 ms |
5440 KB |
Output is correct |
50 |
Correct |
0 ms |
304 KB |
Output is correct |
51 |
Correct |
63 ms |
6572 KB |
Output is correct |
52 |
Correct |
30 ms |
4692 KB |
Output is correct |
53 |
Correct |
50 ms |
4924 KB |
Output is correct |
54 |
Correct |
30 ms |
4796 KB |
Output is correct |
55 |
Correct |
0 ms |
212 KB |
Output is correct |
56 |
Correct |
0 ms |
212 KB |
Output is correct |
57 |
Correct |
0 ms |
212 KB |
Output is correct |
58 |
Correct |
0 ms |
212 KB |
Output is correct |
59 |
Correct |
0 ms |
212 KB |
Output is correct |
60 |
Correct |
0 ms |
212 KB |
Output is correct |
61 |
Correct |
0 ms |
212 KB |
Output is correct |
62 |
Correct |
1 ms |
304 KB |
Output is correct |
63 |
Correct |
0 ms |
212 KB |
Output is correct |
64 |
Correct |
0 ms |
212 KB |
Output is correct |
65 |
Correct |
0 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
212 KB |
Output is correct |
67 |
Correct |
85 ms |
12992 KB |
Output is correct |
68 |
Correct |
53 ms |
4812 KB |
Output is correct |
69 |
Correct |
57 ms |
5040 KB |
Output is correct |
70 |
Correct |
73 ms |
8040 KB |
Output is correct |
71 |
Correct |
86 ms |
16884 KB |
Output is correct |
72 |
Correct |
73 ms |
14700 KB |
Output is correct |
73 |
Correct |
92 ms |
16316 KB |
Output is correct |
74 |
Incorrect |
81 ms |
17068 KB |
3rd lines differ - on the 1st token, expected: '26103122711157', found: '10000000000' |
75 |
Halted |
0 ms |
0 KB |
- |