QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#325553 | #946. Magic Tree | Camillus# | 100 ✓ | 453ms | 94432kb | C++20 | 5.9kb | 2024-02-11 16:48:03 | 2024-07-04 03:23:35 |
Judging History
answer
/// @author Camillus <3
#include "bits/stdc++.h"
using ll = long long;
using namespace std;
int p[100500];
vector<int> g[100500];
int h[100500];
int sz[100500];
void dfs_sz(int u) {
sz[u] = 1;
for (int& v : g[u]) {
dfs_sz(v);
sz[u] += sz[v];
}
}
void dfs_h(int u) {
if (!g[u].empty()) {
for (int v : g[u]) {
h[v] = v;
}
h[g[u].front()] = h[u];
}
for (int v : g[u]) {
dfs_h(v);
}
}
pair<int, int> f[100500];
struct segment_tree {
segment_tree() = default;
static constexpr ll NOP = LLONG_MAX;
struct node {
ll max = 0;
ll add = 0;
ll op = NOP;
};
vector<node> tree;
int n = 0;
segment_tree(int m) {
n = 1;
while (n < m) {
n *= 2;
}
tree.resize(n * 2 - 1);
}
// void apply_add(int x, ll v);
// void apply_op(int x, ll v);
void push(int x) {
if (tree[x].add != 0) {
apply_add(x * 2 + 1, tree[x].add);
apply_add(x * 2 + 2, tree[x].add);
tree[x].add = 0;
}
if (tree[x].op != NOP) {
apply_op(x * 2 + 1, tree[x].op);
apply_op(x * 2 + 2, tree[x].op);
tree[x].op = NOP;
}
}
void apply_add(int x, ll v) {
if (tree[x].op != NOP) {
push(x);
}
tree[x].max += v;
tree[x].add += v;
}
void apply_op(int x, ll v) {
tree[x].max = v;
tree[x].add = 0;
if (x < n - 1) {
tree[x].op = v;
}
}
void pull(int x) {
tree[x].max = max(tree[x * 2 + 1].max, tree[x * 2 + 2].max);
}
void op(int l, int r, ll v, int x = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = n;
}
if (l <= lx && rx <= r) {
apply_op(x, v);
return;
}
if (l >= rx || lx >= r) {
return;
}
push(x);
op(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
op(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);
pull(x);
}
void add(int l, int r, ll v, int x = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = n;
}
if (l <= lx && rx <= r) {
apply_add(x, v);
return;
}
if (l >= rx || lx >= r) {
return;
}
push(x);
add(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
add(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);
pull(x);
}
ll get(int i, int x = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = n;
}
if (rx - lx == 1) {
return tree[x].max;
}
push(x);
if (i < (lx + rx) / 2) {
return get(i, x * 2 + 1, lx, (lx + rx) / 2);
} else {
return get(i, x * 2 + 2, (lx + rx) / 2, rx);
}
}
int lower_bound(ll v, int x = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = n;
}
if (rx - lx == 1) {
return lx;
}
push(x);
if (tree[x * 2 + 1].max >= v) {
return lower_bound(v, x * 2 + 1, lx, (lx + rx) / 2);
} else {
return lower_bound(v, x * 2 + 2, (lx + rx) / 2, rx);
}
}
};
struct ds {
vector<int> keys;
ds() {}
void add_key(int day) {
keys.push_back(day);
}
int n;
segment_tree st;
void build() {
ranges::sort(keys);
keys.erase(unique(keys.begin(), keys.end()), keys.end());
n = (int)keys.size();
st = segment_tree(n);
}
int lower_bound(int key) {
auto i = ranges::lower_bound(keys, key) - keys.begin();
return i;
}
void add(int l, int r, ll v) {
st.add(l, r + 1, v);
}
void op(int l, int r, ll v) {
st.op(l, r + 1, v);
}
ll get(int i) {
return st.get(i);
}
};
ds DS[100500];
void make_ds(int n) {
for (int u = 1; u <= n; u++) {
if (h[u] == u) {
auto dfs = [&r=u](auto &&dfs, int u) -> void {
if (f[u].first) {
DS[r].add_key(f[u].first);
}
for (int v : g[u]) {
dfs(dfs, v);
}
};
dfs(dfs, u);
DS[u].build();
}
}
}
void dfs(int u) {
for (int v : g[u]) {
dfs(v);
if (v != g[u].front()) {
for (int i = 0; i < DS[v].n; i++) {
int L = DS[v].keys[i];
int R = 2'000'000'000;
if (i + 1 != DS[v].n) {
R = DS[v].keys[i + 1];
}
ll D = DS[v].get(i);
L = DS[h[u]].lower_bound(L);
R = DS[h[u]].lower_bound(R);
DS[h[u]].add(L, R - 1, D);
}
}
}
if (f[u].first != 0) {
int i = DS[h[u]].lower_bound(f[u].first);
ll value = DS[h[u]].get(i) + f[u].second;
if (DS[h[u]].get(DS[h[u]].n - 1) <= value) {
DS[h[u]].op(i, DS[h[u]].n - 1, value);
} else {
int j = DS[h[u]].st.lower_bound(value);
assert(DS[h[u]].get(j) >= value);
DS[h[u]].op(i, j - 1, value);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
h[1] = 1;
int n, m, k;
cin >> n >> m >> k;
for (int u = 2; u <= n; u++) {
cin >> p[u];
g[p[u]].push_back(u);
}
for (int i = 0; i < m; i++) {
int u, d, w;
cin >> u >> d >> w;
f[u] = {d, w};
}
dfs_sz(1);
dfs_h(1);
make_ds(n);
dfs(1);
cout << DS[1].get(DS[1].n - 1) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 12584kb
input:
10 9 10 1 1 2 2 3 1 3 8 3 5 4 1 9 4 1 6 8 1 3 1 1 4 9 1 10 1 1 2 6 1 8 7 1 7 9 1
output:
7
result:
ok answer is '7'
Test #2:
score: 0
Accepted
time: 3ms
memory: 11240kb
input:
20 19 20 1 1 2 1 3 6 5 1 5 8 1 10 3 7 4 16 13 4 2 14 13 1 18 9 1 15 16 1 9 20 1 4 18 1 12 15 1 2 6 1 16 13 1 5 5 1 17 19 1 7 4 1 11 14 1 8 3 1 10 1 1 20 16 1 13 1 1 6 4 1 3 12 1 19 20 1
output:
12
result:
ok answer is '12'
Test #3:
score: 0
Accepted
time: 0ms
memory: 12280kb
input:
20 10 10 1 1 3 1 5 2 1 8 2 4 6 9 12 8 15 14 6 5 17 6 7 1 3 6 1 14 5 1 20 7 1 16 7 1 9 6 1 13 4 1 17 1 1 4 2 1 12 7 1
output:
9
result:
ok answer is '9'
Test #4:
score: 0
Accepted
time: 3ms
memory: 11780kb
input:
20 19 8 1 2 3 3 3 5 5 4 4 4 2 11 9 6 3 2 11 2 12 3 6 1 17 8 1 20 6 1 10 7 1 8 5 1 16 5 1 11 2 1 15 5 1 18 8 1 5 4 1 7 8 1 6 4 1 2 4 1 13 1 1 9 6 1 19 7 1 12 7 1 14 2 1 4 8 1
output:
14
result:
ok answer is '14'
Test #5:
score: 0
Accepted
time: 0ms
memory: 13916kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 1 1 3 3 1 4 3 1 5 4 1 6 4 1 7 6 1 8 7 1 9 9 1 10 14 1 11 14 1 12 14 1 13 15 1 14 18 1 15 19 1 16 19 1 17 19 1 18 20 1 19 20 1 20 20 1
output:
3
result:
ok answer is '3'
Test #6:
score: 0
Accepted
time: 0ms
memory: 12844kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 3 1 3 12 1 4 8 1 5 20 1 6 18 1 7 6 1 8 8 1 9 14 1 10 7 1 11 5 1 12 14 1 13 13 1 14 11 1 15 7 1 16 15 1 17 18 1 18 5 1 19 10 1 20 13 1
output:
8
result:
ok answer is '8'
Test #7:
score: 0
Accepted
time: 0ms
memory: 12360kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 20 1 3 17 1 4 15 1 5 14 1 6 9 1 7 9 1 8 7 1 9 7 1 10 6 1 11 4 1 12 4 1 13 4 1 14 3 1 15 3 1 16 2 1 17 2 1 18 2 1 19 1 1 20 1 1
output:
19
result:
ok answer is '19'
Test #8:
score: 0
Accepted
time: 0ms
memory: 12768kb
input:
20 15 20 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 14 1 7 6 1 20 3 1 3 1 1 18 7 1 10 10 1 11 3 1 12 17 1 9 14 1 8 12 1 5 12 1 13 14 1 4 11 1 15 14 1 17 5 1
output:
14
result:
ok answer is '14'
Test #9:
score: 0
Accepted
time: 0ms
memory: 11292kb
input:
20 15 20 1 2 3 4 2 6 7 5 8 5 10 12 11 11 13 16 15 18 19 2 11 1 12 15 1 15 1 1 20 12 1 13 16 1 10 6 1 4 6 1 11 19 1 18 13 1 3 14 1 7 15 1 16 11 1 9 12 1 14 3 1 5 19 1
output:
9
result:
ok answer is '9'
Subtask #2:
score: 3
Accepted
Test #10:
score: 3
Accepted
time: 95ms
memory: 27236kb
input:
100000 25000 100000 1 1 2 1 2 1 5 8 8 2 5 2 2 3 1 2 11 10 18 2 9 9 9 8 1 19 18 22 20 17 20 13 30 5 9 8 13 2 19 26 14 31 23 22 2 21 8 1 22 9 50 19 49 42 47 19 21 57 9 52 41 39 10 14 60 56 34 17 18 22 53 5 34 64 29 72 33 11 9 67 58 10 58 70 57 26 65 10 15 64 67 20 26 13 51 81 11 78 40 53 70 33 34 92 7...
output:
12471468294549
result:
ok answer is '12471468294549'
Test #11:
score: 0
Accepted
time: 46ms
memory: 30820kb
input:
100000 20000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
10044081452141
result:
ok answer is '10044081452141'
Test #12:
score: 0
Accepted
time: 303ms
memory: 67992kb
input:
100000 90000 100000 1 1 1 1 1 1 1 1 8 1 1 8 11 11 4 4 8 11 4 4 11 4 8 8 24 4 23 4 4 11 23 11 11 1 24 24 11 23 23 23 4 24 24 11 8 11 24 23 8 24 50 1 24 23 4 24 1 4 1 11 11 50 57 23 23 54 53 55 61 23 69 54 67 11 69 24 75 23 1 53 75 1 75 1 75 50 55 61 57 55 55 23 89 8 55 11 77 89 11 24 61 23 1 75 89 67...
output:
44983082712726
result:
ok answer is '44983082712726'
Test #13:
score: 0
Accepted
time: 77ms
memory: 22696kb
input:
100000 90000 100000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
45049819058025
result:
ok answer is '45049819058025'
Test #14:
score: 0
Accepted
time: 101ms
memory: 24144kb
input:
100000 90000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
44931255444152
result:
ok answer is '44931255444152'
Subtask #3:
score: 11
Accepted
Test #15:
score: 11
Accepted
time: 0ms
memory: 12080kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
3
result:
ok answer is '3'
Test #16:
score: 0
Accepted
time: 4ms
memory: 14260kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
38
result:
ok answer is '38'
Test #17:
score: 0
Accepted
time: 3ms
memory: 12676kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
500
result:
ok answer is '500'
Test #18:
score: 0
Accepted
time: 80ms
memory: 48628kb
input:
100000 99999 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
7
result:
ok answer is '7'
Test #19:
score: 0
Accepted
time: 62ms
memory: 48636kb
input:
100000 99999 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
99999
result:
ok answer is '99999'
Test #20:
score: 0
Accepted
time: 121ms
memory: 48524kb
input:
100000 99999 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
624
result:
ok answer is '624'
Subtask #4:
score: 12
Accepted
Test #21:
score: 12
Accepted
time: 76ms
memory: 21508kb
input:
100000 90000 2 1 1 3 2 1 2 1 5 1 8 11 9 1 8 12 7 1 2 7 6 12 9 16 18 13 10 23 27 26 17 23 10 24 11 21 13 30 1 11 6 13 8 30 15 17 34 39 41 32 29 27 17 21 12 26 33 10 50 29 17 46 33 21 28 47 26 3 67 38 5 10 45 61 70 59 17 46 40 20 58 67 68 15 62 71 71 57 32 81 18 66 7 14 51 67 92 86 38 88 60 45 54 5 59...
output:
38521956905095
result:
ok answer is '38521956905095'
Test #22:
score: 0
Accepted
time: 74ms
memory: 21028kb
input:
100000 90000 1 1 1 2 2 5 1 2 7 3 6 3 7 8 6 11 1 17 11 15 1 11 3 7 4 11 12 20 5 14 17 29 4 6 27 29 1 9 11 1 5 23 42 36 10 16 39 34 14 31 5 22 48 43 43 1 34 51 26 10 16 22 15 42 8 63 27 57 16 50 60 23 67 44 13 40 60 49 55 77 73 44 32 80 50 26 20 24 72 75 21 47 74 24 67 59 43 19 17 85 61 12 99 21 104 1...
output:
44817789931778
result:
ok answer is '44817789931778'
Test #23:
score: 0
Accepted
time: 57ms
memory: 30060kb
input:
100000 90000 2 1 2 3 2 5 5 4 7 9 8 11 10 3 12 15 10 17 16 18 3 19 20 23 24 2 22 25 10 28 27 30 31 32 33 35 34 37 36 24 39 41 42 43 44 38 20 9 45 49 50 46 52 52 30 51 53 57 58 56 59 23 31 60 64 65 66 67 61 28 69 71 72 41 73 68 75 77 12 5 76 4 78 77 51 81 83 87 7 88 86 28 91 93 90 94 96 95 98 99 100 9...
output:
27165432883093
result:
ok answer is '27165432883093'
Test #24:
score: 0
Accepted
time: 23ms
memory: 19464kb
input:
100000 90000 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...
output:
44981598598688
result:
ok answer is '44981598598688'
Test #25:
score: 0
Accepted
time: 37ms
memory: 45612kb
input:
100000 90000 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
22589648566145
result:
ok answer is '22589648566145'
Subtask #5:
score: 12.5
Accepted
Dependency #1:
100%
Accepted
Test #26:
score: 12.5
Accepted
time: 104ms
memory: 27396kb
input:
100000 90000 20 1 2 3 3 3 4 6 2 7 3 4 6 10 6 13 1 11 7 8 18 1 19 7 4 9 4 20 9 26 9 6 5 23 2 23 11 5 17 28 19 14 34 36 43 32 10 41 1 19 28 35 6 40 6 23 15 6 32 15 15 21 6 30 62 51 11 46 45 21 2 41 31 8 9 9 9 25 26 79 68 66 4 52 6 64 6 52 52 67 74 80 15 39 58 11 90 2 53 12 45 75 61 62 61 57 19 95 50 1...
output:
62571
result:
ok answer is '62571'
Test #27:
score: 0
Accepted
time: 95ms
memory: 25728kb
input:
100000 90000 10 1 1 1 4 2 5 5 8 2 5 4 7 7 1 7 16 1 13 18 5 13 15 6 24 10 16 20 22 25 17 23 31 22 25 29 8 4 20 24 40 26 10 26 23 10 13 12 34 41 16 9 21 51 17 50 32 54 12 35 51 4 27 48 18 43 42 49 29 30 64 29 25 58 64 73 61 45 24 78 6 26 33 34 68 44 22 83 11 73 59 13 58 3 87 3 55 72 14 37 37 5 40 3 21...
output:
63666
result:
ok answer is '63666'
Test #28:
score: 0
Accepted
time: 74ms
memory: 30152kb
input:
100000 90000 20 1 2 2 3 5 3 4 4 6 9 10 12 13 14 11 16 3 17 19 20 21 15 19 23 22 25 16 27 26 27 31 32 30 33 35 36 34 37 38 40 41 42 39 44 43 45 46 47 49 22 32 50 48 20 53 54 57 56 59 58 61 62 63 25 60 66 67 64 68 69 71 72 19 46 70 76 77 73 79 2 80 78 83 82 35 85 87 84 88 89 91 90 73 93 92 95 96 17 57...
output:
21768
result:
ok answer is '21768'
Test #29:
score: 0
Accepted
time: 34ms
memory: 18092kb
input:
100000 90000 20 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
89999
result:
ok answer is '89999'
Test #30:
score: 0
Accepted
time: 39ms
memory: 45680kb
input:
100000 90000 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
5018
result:
ok answer is '5018'
Subtask #6:
score: 13
Accepted
Test #31:
score: 13
Accepted
time: 4ms
memory: 12916kb
input:
20000 800 60000 1 1 1 2 3 1 7 8 6 1 7 6 1 7 14 16 11 13 14 3 11 11 4 2 5 24 20 24 16 30 15 3 24 31 12 7 2 29 14 25 39 23 16 33 32 33 34 9 13 37 33 23 15 21 28 39 51 19 6 50 54 55 8 40 3 7 34 19 28 15 61 18 22 28 38 15 47 37 42 73 38 61 10 7 30 58 41 43 69 89 62 84 30 68 92 84 43 59 44 75 8 100 83 18...
output:
386917987664
result:
ok answer is '386917987664'
Test #32:
score: 0
Accepted
time: 39ms
memory: 17728kb
input:
100000 770 60000 1 2 3 3 2 2 4 7 9 9 3 11 6 6 13 12 4 4 7 11 20 17 1 22 15 1 10 21 9 23 31 22 12 24 16 26 29 9 36 13 8 5 41 38 34 19 31 29 13 32 11 39 38 32 26 38 39 29 38 6 49 59 3 9 18 38 42 20 38 11 45 8 68 19 51 66 53 7 26 35 56 60 35 32 45 57 45 27 64 49 46 64 13 64 4 49 32 22 45 67 67 62 70 10...
output:
372407653338
result:
ok answer is '372407653338'
Test #33:
score: 0
Accepted
time: 38ms
memory: 17724kb
input:
100000 770 90000 1 1 3 4 5 3 4 8 7 4 9 4 8 7 1 8 2 5 15 12 4 8 12 18 1 12 26 9 16 19 28 5 5 15 35 25 29 8 1 20 24 31 14 29 43 11 27 46 22 8 27 29 43 13 44 14 24 15 2 38 22 57 15 44 63 17 49 30 60 30 57 24 49 29 29 14 72 36 17 37 76 78 5 2 44 59 4 67 65 29 64 59 87 46 95 2 70 80 41 39 11 69 86 93 33 ...
output:
391025345374
result:
ok answer is '391025345374'
Test #34:
score: 0
Accepted
time: 37ms
memory: 17692kb
input:
100000 1000 90000 1 2 3 1 3 3 4 6 3 5 5 3 9 3 12 14 2 6 15 2 15 14 14 8 12 7 26 13 12 23 15 1 29 2 11 34 18 26 37 23 23 26 12 9 3 32 31 38 33 21 50 25 50 24 9 51 6 9 15 5 8 25 39 3 17 42 21 54 50 25 37 59 42 16 43 15 55 43 79 17 67 57 26 19 46 86 87 9 56 7 65 31 86 11 64 72 38 71 44 86 76 66 58 83 5...
output:
479762613817
result:
ok answer is '479762613817'
Test #35:
score: 0
Accepted
time: 7ms
memory: 15476kb
input:
100000 1000 100000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...
output:
505184101665
result:
ok answer is '505184101665'
Test #36:
score: 0
Accepted
time: 60ms
memory: 23752kb
input:
100000 1000 100000 1 2 2 3 4 2 6 1 6 8 3 11 2 6 11 13 12 12 11 19 1 12 2 17 21 26 25 27 28 25 30 8 8 29 28 26 12 11 3 32 6 2 21 41 35 25 29 8 46 12 26 46 28 19 25 26 6 45 32 59 29 50 61 28 61 6 2 63 69 19 8 1 66 30 12 17 2 69 66 27 41 63 59 35 79 74 86 41 13 11 29 1 4 46 11 25 69 11 88 87 17 88 3 10...
output:
335049254491
result:
ok answer is '335049254491'
Test #37:
score: 0
Accepted
time: 27ms
memory: 28784kb
input:
100000 1000 100000 1 2 2 4 5 3 7 6 8 10 10 12 13 9 15 8 16 18 9 19 12 21 14 24 23 26 10 25 27 29 3 31 4 18 33 30 37 33 36 40 38 29 42 41 44 45 27 47 5 46 49 52 51 51 55 53 56 58 59 60 4 9 61 57 65 64 66 67 59 69 52 24 68 74 71 75 33 77 76 79 80 82 81 5 83 45 84 88 89 77 90 86 71 92 95 93 97 96 98 10...
output:
136740610217
result:
ok answer is '136740610217'
Subtask #7:
score: 22
Accepted
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #38:
score: 22
Accepted
time: 29ms
memory: 19268kb
input:
20000 18000 2000 1 1 2 3 5 4 6 7 4 6 9 11 2 5 15 3 4 15 4 19 1 18 13 3 5 14 9 1 19 24 7 3 9 16 35 34 15 10 14 40 28 41 36 22 42 43 24 6 28 41 33 11 11 11 53 20 20 3 48 26 27 15 24 7 13 21 7 55 26 38 3 66 73 29 12 39 71 6 6 11 47 42 25 12 59 10 86 23 68 28 82 71 59 36 65 92 17 63 75 68 85 95 26 53 79...
output:
12204
result:
ok answer is '12204'
Test #39:
score: 0
Accepted
time: 126ms
memory: 30144kb
input:
100000 47000 2000 1 1 2 3 5 6 7 6 2 6 5 9 4 2 12 9 13 15 15 20 14 20 13 8 5 3 7 12 1 10 26 29 22 16 9 19 37 28 34 9 5 11 6 12 41 9 8 28 15 27 11 2 25 5 49 8 45 55 20 16 13 40 28 30 13 6 45 65 12 45 9 46 14 50 45 65 49 58 42 10 37 30 77 1 70 73 23 34 70 49 54 74 20 30 47 9 63 81 13 18 30 39 14 29 15 ...
output:
35611
result:
ok answer is '35611'
Test #40:
score: 0
Accepted
time: 160ms
memory: 37396kb
input:
100000 47000 90000 1 2 1 3 2 4 6 6 9 9 6 6 3 9 13 13 8 5 2 12 17 15 19 5 22 18 12 15 24 11 29 22 31 32 17 9 20 16 36 10 33 31 33 13 32 10 5 10 43 15 16 10 39 33 31 46 10 52 18 4 16 26 9 15 3 14 35 63 22 21 20 31 34 46 19 34 41 9 30 30 41 33 31 4 57 9 67 30 74 11 8 60 72 59 88 80 55 41 19 22 63 19 82...
output:
35664
result:
ok answer is '35664'
Test #41:
score: 0
Accepted
time: 249ms
memory: 52564kb
input:
100000 90000 90000 1 1 2 2 3 2 2 1 9 8 11 5 13 10 14 2 15 14 13 18 16 18 7 12 1 7 23 26 5 30 27 26 15 32 9 5 18 27 16 27 26 14 32 44 36 22 34 42 49 50 25 9 31 12 49 22 30 44 51 12 41 3 24 10 39 36 23 10 46 26 50 52 16 55 36 46 16 68 62 49 6 62 57 26 10 38 31 14 73 47 35 5 9 34 75 57 2 3 8 72 57 75 3...
output:
61203
result:
ok answer is '61203'
Test #42:
score: 0
Accepted
time: 72ms
memory: 22500kb
input:
100000 90000 100000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
89999
result:
ok answer is '89999'
Test #43:
score: 0
Accepted
time: 453ms
memory: 93484kb
input:
100000 90000 100000 1 2 2 1 2 1 1 2 6 10 1 10 9 9 1 9 2 1 14 10 14 11 2 14 2 14 11 9 10 1 28 25 28 9 33 1 34 33 9 6 28 38 28 36 45 43 47 48 46 49 48 45 51 1 50 38 51 58 58 56 59 38 10 61 14 43 62 62 65 69 58 11 70 74 75 28 49 47 6 33 58 71 75 83 61 56 76 85 88 90 89 92 59 38 93 74 61 61 76 14 91 96 ...
output:
54089
result:
ok answer is '54089'
Test #44:
score: 0
Accepted
time: 172ms
memory: 40760kb
input:
100000 90000 100000 1 2 2 4 5 3 6 7 8 10 11 9 13 12 15 14 14 17 19 1 16 22 20 23 24 12 26 28 25 1 29 32 30 33 24 35 34 38 37 9 17 39 25 40 45 5 24 5 46 43 50 52 51 54 53 56 57 58 52 55 59 61 24 63 12 65 62 65 68 67 46 70 73 74 75 76 71 77 79 80 56 81 35 78 83 53 85 88 24 89 91 92 1 93 12 86 97 95 98...
output:
18326
result:
ok answer is '18326'
Subtask #8:
score: 17
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Test #45:
score: 17
Accepted
time: 36ms
memory: 17792kb
input:
20000 18000 2000 1 2 2 2 5 3 6 1 3 9 3 2 10 7 6 5 9 4 16 15 16 1 6 19 3 2 16 3 7 26 31 11 27 31 16 22 18 14 33 39 36 39 36 21 42 25 15 47 3 41 30 26 47 33 49 14 10 7 54 9 20 2 49 11 19 27 26 47 16 60 37 40 34 24 47 13 5 65 46 22 35 51 73 29 25 77 76 54 30 35 32 47 83 18 42 72 13 80 45 76 11 95 80 22...
output:
6578253117438
result:
ok answer is '6578253117438'
Test #46:
score: 0
Accepted
time: 122ms
memory: 30308kb
input:
100000 47000 2000 1 1 3 2 4 5 1 4 1 5 2 12 10 3 11 16 1 9 13 13 7 5 11 20 1 12 24 8 26 11 9 30 33 21 34 16 6 23 4 27 9 19 42 9 40 4 42 40 39 44 14 21 53 28 25 26 27 53 34 56 29 17 49 5 58 59 1 43 2 25 47 24 11 31 13 12 37 52 64 14 81 2 65 71 43 3 65 53 43 83 1 53 24 16 22 89 40 45 22 88 77 56 49 49 ...
output:
18773912893303
result:
ok answer is '18773912893303'
Test #47:
score: 0
Accepted
time: 136ms
memory: 35132kb
input:
100000 47000 90000 1 1 2 2 4 6 7 1 5 5 7 8 2 7 3 7 6 8 8 4 4 13 6 7 5 18 6 26 18 18 18 10 11 20 1 9 20 14 32 34 40 4 18 40 33 22 27 15 1 41 20 1 17 6 28 50 16 12 23 60 42 44 52 12 15 33 67 52 41 43 1 47 25 49 45 56 39 23 16 75 40 19 65 26 29 72 66 25 86 31 59 42 34 75 73 50 39 85 76 11 78 62 71 104 ...
output:
18951144895815
result:
ok answer is '18951144895815'
Test #48:
score: 0
Accepted
time: 255ms
memory: 53196kb
input:
100000 90000 90000 1 2 2 1 5 1 1 4 7 2 6 4 12 4 5 12 12 12 7 18 12 16 14 22 13 11 16 5 12 8 20 14 24 20 28 32 23 31 19 27 25 29 17 38 37 22 45 47 7 31 29 51 9 16 18 50 4 8 16 52 6 29 4 7 55 5 13 51 22 49 22 28 6 58 53 68 15 4 63 62 54 44 26 55 24 31 14 9 40 66 87 91 64 8 48 91 82 47 65 65 83 15 62 7...
output:
32722313440266
result:
ok answer is '32722313440266'
Test #49:
score: 0
Accepted
time: 66ms
memory: 23544kb
input:
100000 90000 100000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
44913169784229
result:
ok answer is '44913169784229'
Test #50:
score: 0
Accepted
time: 439ms
memory: 94432kb
input:
100000 90000 100000 1 2 2 2 5 3 3 3 7 5 3 2 5 10 2 5 5 3 15 18 10 2 18 5 21 15 26 27 29 3 10 27 26 1 15 1 26 2 10 3 30 42 30 26 21 43 45 27 47 50 48 52 45 53 18 55 10 48 57 51 10 50 61 42 64 57 21 43 2 67 71 10 21 66 26 72 75 77 78 57 67 78 45 52 80 86 7 87 89 90 61 91 79 94 5 55 93 95 95 98 57 94 7...
output:
27024000655737
result:
ok answer is '27024000655737'
Test #51:
score: 0
Accepted
time: 217ms
memory: 50152kb
input:
100000 90000 100000 1 2 3 2 4 6 7 2 1 8 5 5 13 14 11 16 17 17 15 20 21 14 16 22 25 16 26 28 6 29 4 18 33 31 35 31 34 38 36 40 36 31 41 39 45 46 6 47 44 50 49 51 52 53 54 55 56 58 45 59 61 21 57 46 64 62 67 68 66 69 71 70 72 73 75 74 76 25 77 80 81 82 38 83 85 78 87 86 2 89 88 91 92 93 44 95 14 97 94...
output:
9216936040376
result:
ok answer is '9216936040376'