QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325529#946. Magic TreeCamillus#46.5 160ms31092kbC++203.3kb2024-02-11 16:17:042024-07-04 03:23:34

Judging History

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

  • [2024-07-04 03:23:34]
  • 评测
  • 测评结果:46.5
  • 用时:160ms
  • 内存:31092kb
  • [2024-02-11 16:17:04]
  • 提交

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 ds {
    vector<int> keys = {0};
    ds() {}

    void add_key(int day) {
        keys.push_back(day);
    }

    vector<ll> tree;
    int n;

    void build() {
        ranges::sort(keys);
        keys.erase(unique(keys.begin(), keys.end()), keys.end());
        n = (int)keys.size();
        tree.resize(n + 1);
    }

    int lower_bound(int key) {
        auto i = ranges::lower_bound(keys, key) - keys.begin();
        return i;
    }

    int upper_bound(int key) {
        auto i = ranges::lower_bound(keys, key) - keys.begin();
        return i;
    }

    void add(int l, int r, ll v) {
        for (int i = l; i < n; i += i & -i) {
            tree[i] += v;
        }

        for (int i = r + 1; i < n; i += i & -i) {
            tree[i] -= v;
        }
    }

    ll get(int i) const {
        ll res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }
};

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 = 1; 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;

        for (; i < DS[h[u]].n; i++) {
            ll cur = DS[h[u]].get(i);
            if (cur < value) {
                DS[h[u]].add(i, i, value - cur);
            } else {
                break;
            }
        }
    }
}

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: 5ms
memory: 13620kb

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: 0ms
memory: 16516kb

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: 3ms
memory: 15136kb

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: 0ms
memory: 13896kb

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: 3ms
memory: 15308kb

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: 6ms
memory: 15256kb

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: 2ms
memory: 15380kb

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

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

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: 63ms
memory: 21416kb

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: 36ms
memory: 23424kb

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: 160ms
memory: 28320kb

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: 40ms
memory: 19148kb

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: 49ms
memory: 19368kb

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: 0
Time Limit Exceeded

Test #15:

score: 11
Accepted
time: 0ms
memory: 14044kb

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: 3ms
memory: 14016kb

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: 6ms
memory: 15412kb

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: 38ms
memory: 31092kb

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: -11
Time Limit Exceeded

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:


Subtask #4:

score: 12
Accepted

Test #21:

score: 12
Accepted
time: 60ms
memory: 21868kb

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: 55ms
memory: 21912kb

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: 47ms
memory: 24616kb

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

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: 30ms
memory: 30940kb

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: 88ms
memory: 22812kb

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: 82ms
memory: 22504kb

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: 60ms
memory: 24912kb

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: 28ms
memory: 17792kb

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: 51ms
memory: 30668kb

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: 7ms
memory: 15512kb

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: 34ms
memory: 19668kb

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: 40ms
memory: 19696kb

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: 41ms
memory: 19708kb

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: 9ms
memory: 18192kb

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: 51ms
memory: 22040kb

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: 24ms
memory: 23968kb

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: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%