QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#71811	#946. Magic Tree	He_Ren	100 ✓	154ms	46040kb	C++23	2.3kb	2023-01-12 01:21:04	2023-01-12 01:22:58

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-01-12 01:22:58]
评测

测评结果：100
用时：154ms
内存：46040kb

查看

[2023-01-12 01:21:04]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXP = MAXN * 20;

namespace SegT {
int ls[MAXP], rs[MAXP], pcnt = 0;
ll mx[MAXP], tag[MAXP];
#define lson(u) ls[u],l,mid
#define rson(u) rs[u],mid+1,r
inline void push_up(int u) {
    mx[u] = max(mx[ls[u]], mx[rs[u]]);
}
inline void upd(int u, ll k) {
    if (!u)
        return;

    tag[u] += k;
    mx[u] += k;
}
inline void push_down(int u) {
    if (tag[u]) {
        upd(ls[u], tag[u]);
        upd(rs[u], tag[u]);
        tag[u] = 0;
    }
}
void update(int &u, int l, int r, int q, ll k, ll pre) {
    if (!u)
        u = ++pcnt;

    if (l == r) {
        mx[u] = max(mx[u], pre) + k;
        return;
    }

    push_down(u);
    int mid = (l + r) >> 1;

    if (q <= mid)
        update(lson(u), q, k, pre);
    else
        update(rson(u), q, k, max(pre, mx[ls[u]]));

    push_up(u);
}
void merge(int &u, int l, int r, int v, ll preu, ll prev) {
    if (!u && !v)
        return;

    if (!u) {
        upd(u = v, preu);
        return;
    }

    if (!v) {
        upd(u, prev);
        return;
    }

    if (l == r) {
        mx[u] = max(mx[u], preu) + max(mx[v], prev);
        return;
    }

    push_down(u);
    push_down(v);
    int mid = (l + r) >> 1;
    merge(rson(u), rs[v], max(preu, mx[ls[u]]), max(prev, mx[ls[v]]));
    merge(lson(u), ls[v], preu, prev);
    push_up(u);
}

int n;
inline void update(int &u, int q, ll k) {
    update(u, 1, n, q, k, 0);
}
inline void merge(int &u, int v) {
    merge(u, 1, n, v, 0, 0);
}
}

vector<int> g[MAXN];
int a[MAXN], b[MAXN];

int rt[MAXN];
void dfs_res(int u) {
    for (int v : g[u]) {
        dfs_res(v);
        SegT::merge(rt[u], rt[v]);
    }

    if (b[u])
        SegT::update(rt[u], a[u], b[u]);
}

int main(void) {
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);

    for (int i = 2; i <= n; ++i) {
        int j;
        scanf("%d", &j);
        g[j].push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        int u, x, y;
        scanf("%d%d%d", &u, &x, &y);
        a[u] = x;
        b[u] = y;
    }

    SegT::n = d;
    dfs_res(1);

    printf("%lld", SegT::mx[rt[1]]);
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 2ms

memory: 7692kb

input:

output:

result:

ok answer is '7'

Test #2:

score: 0

Accepted

time: 0ms

memory: 6264kb

input:

output:

result:

ok answer is '12'

Test #3:

score: 0

Accepted

time: 1ms

memory: 7696kb

input:

output:

result:

ok answer is '9'

Test #4:

score: 0

Accepted

time: 1ms

memory: 7800kb

input:

output:

result:

ok answer is '14'

Test #5:

score: 0

Accepted

time: 1ms

memory: 7924kb

input:

output:

result:

ok answer is '3'

Test #6:

score: 0

Accepted

time: 1ms

memory: 7952kb

input:

output:

result:

ok answer is '8'

Test #7:

score: 0

Accepted

time: 4ms

memory: 7660kb

input:

output:

result:

ok answer is '19'

Test #8:

score: 0

Accepted

time: 3ms

memory: 6356kb

input:

output:

result:

ok answer is '14'

Test #9:

score: 0

Accepted

time: 2ms

memory: 7756kb

input:

output:

result:

ok answer is '9'

Subtask #2:

score: 3

Accepted

Test #10:

score: 3

Accepted

time: 64ms

memory: 18984kb

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: 39ms

memory: 20408kb

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: 121ms

memory: 45300kb

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: 116ms

memory: 44592kb

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: 154ms

memory: 46040kb

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: 8180kb

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:

result:

ok answer is '3'

Test #16:

score: 0

Accepted

time: 0ms

memory: 6604kb

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:

result:

ok answer is '38'

Test #17:

score: 0

Accepted

time: 0ms

memory: 7828kb

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:

result:

ok answer is '500'

Test #18:

score: 0

Accepted

time: 55ms

memory: 21760kb

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:

result:

ok answer is '7'

Test #19:

score: 0

Accepted

time: 51ms

memory: 21916kb

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:

result:

ok answer is '99999'

Test #20:

score: 0

Accepted

time: 59ms

memory: 20864kb

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:

result:

ok answer is '624'

Subtask #4:

score: 12

Accepted

Test #21:

score: 12

Accepted

time: 45ms

memory: 11476kb

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: 42ms

memory: 10284kb

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: 34ms

memory: 15232kb

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: 37ms

memory: 10148kb

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: 44ms

memory: 18764kb

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: 59ms

memory: 16996kb

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:

result:

ok answer is '62571'

Test #27:

score: 0

Accepted

time: 54ms

memory: 15032kb

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:

result:

ok answer is '63666'

Test #28:

score: 0

Accepted

time: 34ms

memory: 15580kb

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:

result:

ok answer is '21768'

Test #29:

score: 0

Accepted

time: 34ms

memory: 15336kb

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:

result:

ok answer is '89999'

Test #30:

score: 0

Accepted

time: 26ms

memory: 18500kb

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:

result:

ok answer is '5018'

Subtask #6:

score: 13

Accepted

Test #31:

score: 13

Accepted

time: 1ms

memory: 8736kb

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: 17ms

memory: 10948kb

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: 17ms

memory: 9616kb

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: 12ms

memory: 10700kb

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: 8ms

memory: 7920kb

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: 21ms

memory: 10456kb

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: 17ms

memory: 14644kb

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: 19ms

memory: 11544kb

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:

result:

ok answer is '12204'

Test #39:

score: 0

Accepted

time: 55ms

memory: 20852kb

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:

result:

ok answer is '35611'

Test #40:

score: 0

Accepted

time: 69ms

memory: 26812kb

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:

result:

ok answer is '35664'

Test #41:

score: 0

Accepted

time: 127ms

memory: 42348kb

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:

result:

ok answer is '61203'

Test #42:

score: 0

Accepted

time: 120ms

memory: 44756kb

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:

result:

ok answer is '89999'

Test #43:

score: 0

Accepted

time: 100ms

memory: 35128kb

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:

result:

ok answer is '54089'

Test #44:

score: 0

Accepted

time: 70ms

memory: 24764kb

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:

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: 11ms

memory: 11268kb

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: 65ms

memory: 20652kb

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: 70ms

memory: 26764kb

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: 137ms

memory: 42292kb

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: 135ms

memory: 44580kb

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: 112ms

memory: 35132kb

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: 86ms

memory: 24748kb

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'