oj.uz

Submission #520466

# Submission time Handle Problem Language Result Execution time Memory
520466 2022-01-30T05:50:48 Z KoD Diversity (CEOI21_diversity) C++17
64 / 100
 7000 ms 280176 KB 
#include <bits/stdc++.h>
 
using std::vector;
using std::array;
using std::pair;
using std::tuple;
 
using i64 = std::int64_t;
 
constexpr int B = 700;
constexpr int MAX = 300000;
 
constexpr i64 sum_k(const int n) {
    return (i64)n * (n + 1) / 2;
}
 
constexpr i64 sum_k2(const int n) {
    return (i64)n * (n + 1) * (2 * n + 1) / 6;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
        x -= 1;
    }
    const int G = N / B;
    vector precalc(G + 1, vector<vector<pair<int, int>>>(G + 1));
    for (int lc = 0; lc < G; ++lc) {
        vector<char> appear(MAX);
        vector<int> count(MAX);
        for (int rc = lc + 1; rc <= G; ++rc) {
            vector<int> remove, add;
            for (int i = B * (rc - 1); i < B * rc; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    if (count[A[i]] > 0) {
                        remove.push_back(count[A[i]]);
                    }
                    add.push_back(A[i]);
                }
                count[A[i]] += 1;
            }
            for (auto& x : add) {
                appear[x] = false;
                x = count[x];
            }
            std::sort(remove.begin(), remove.end());
            std::sort(add.begin(), add.end());
            const auto& read = precalc[lc][rc - 1];
            auto& write = precalc[lc][rc];
            const int A = read.size(), B = remove.size(), C = add.size();
            int i = 0, j = 0, k = 0;
            while (i < A or k < C) {
                int val = MAX;
                if (i < A) {
                    val = std::min(val, read[i].first);
                }
                if (k < C) {
                    val = std::min(val, add[k]);
                }
                int cnt = 0;
                if (i < A and val == read[i].first) {
                    cnt += read[i].second;
                    i += 1;
                }
                while (j < B and val == remove[j]) {
                    j += 1;
                    cnt -= 1;
                }
                while (k < C and val == add[k]) {
                    k += 1;
                    cnt += 1;
                }
                if (cnt > 0) {
                    write.emplace_back(val, cnt);
                }
            }
        }
    }
    vector<vector<int>> idx(MAX);
    for (int i = 0; i < N; ++i) {
        idx[A[i]].push_back(i);
    }
    const auto range_count = [&](const int l, const int r, const int x) {
        const auto& v = idx[x];
        return std::lower_bound(v.begin(), v.end(), r) - std::lower_bound(v.begin(), v.end(), l);
    };
    vector<char> appear(MAX);
    vector<int> count(MAX);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        l -= 1;
        vector<pair<int, int>> list;
        if (l / B == r / B) {
            vector<int> add;
            for (int i = l; i < r; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    add.push_back(A[i]);
                }
                count[A[i]] += 1;
            }
            for (const int x : add) {
                appear[x] = false;
                list.emplace_back(count[x], 1);
                count[x] = 0;
            }
            std::sort(list.begin(), list.end());
        } else {
            const int lc = (l + B - 1) / B;
            const int rc = r / B;
            assert(lc <= rc);
            vector<int> remove, add, seen;
            for (int i = l; i < B * lc; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    const int tmp = range_count(B * lc, B * rc, A[i]);
                    if (tmp > 0) {
                        remove.push_back(tmp);
                    }
                    add.push_back(range_count(l, r, A[i]));
                    seen.push_back(A[i]);
                }
            } 
            for (int i = B * rc; i < r; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    const int tmp = range_count(B * lc, B * rc, A[i]);
                    if (tmp > 0) {
                        remove.push_back(tmp);
                    }
                    add.push_back(range_count(l, r, A[i]));
                    seen.push_back(A[i]);
                }
            } 
            for (const int x : seen) {
                appear[x] = false;
            }
            std::sort(remove.begin(), remove.end());
            std::sort(add.begin(), add.end());
            const auto& read = precalc[lc][rc];
            const int A = read.size(), B = remove.size(), C = add.size();
            int i = 0, j = 0, k = 0;
            while (i < A or k < C) {
                int val = MAX;
                if (i < A) {
                    val = std::min(val, read[i].first);
                }
                if (k < C) {
                    val = std::min(val, add[k]);
                }
                int cnt = 0;
                if (i < A and val == read[i].first) {
                    cnt += read[i].second;
                    i += 1;
                }
                while (j < B and val == remove[j]) {
                    j += 1;
                    cnt -= 1;
                }
                while (k < C and val == add[k]) {
                    k += 1;
                    cnt += 1;
                }
                if (cnt > 0) {
                    list.emplace_back(val, cnt);
                }
            }
        }
        const int len = r - l;
        i64 ans = sum_k(len);
        const auto add_to = [&](const i64 s, const int a, const int n) {
            ans += (n * s + sum_k(n) * a) * len;
            ans -= n * s * s + 2 * s * sum_k(n) * a + sum_k2(n) * a * a;
        };
        int left = 0, right = 0;
        for (const auto& [a, b] : list) {
            assert(a > 0 and b > 0);
            if (left > right) {
                std::swap(left, right);
            }
            const int need = std::min(b, (right - left + a - 1) / a);
            const int to_left = need + (b - need) / 2;
            const int to_right = b - to_left;
            add_to(left, a, to_left);
            add_to(right, a, to_right);
            left += a * to_left;
            right += a * to_right;
        }
        ans -= (i64)left * (len - left);
        std::cout << ans << '\n';
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 5 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 6 ms 8848 KB Output is correct
3 Correct 6 ms 10008 KB Output is correct
4 Correct 48 ms 12276 KB Output is correct
5 Correct 159 ms 18624 KB Output is correct
6 Correct 337 ms 29184 KB Output is correct
7 Correct 329 ms 28960 KB Output is correct
8 Correct 335 ms 29280 KB Output is correct
9 Correct 338 ms 28876 KB Output is correct
10 Correct 322 ms 28864 KB Output is correct
11 Correct 346 ms 28868 KB Output is correct
12 Correct 365 ms 28980 KB Output is correct
13 Correct 337 ms 29212 KB Output is correct
14 Correct 350 ms 29316 KB Output is correct
15 Correct 332 ms 28888 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 6 ms 8848 KB Output is correct
3 Correct 6 ms 10008 KB Output is correct
4 Correct 48 ms 12276 KB Output is correct
5 Correct 159 ms 18624 KB Output is correct
6 Correct 337 ms 29184 KB Output is correct
7 Correct 329 ms 28960 KB Output is correct
8 Correct 335 ms 29280 KB Output is correct
9 Correct 338 ms 28876 KB Output is correct
10 Correct 322 ms 28864 KB Output is correct
11 Correct 346 ms 28868 KB Output is correct
12 Correct 365 ms 28980 KB Output is correct
13 Correct 337 ms 29212 KB Output is correct
14 Correct 350 ms 29316 KB Output is correct
15 Correct 332 ms 28888 KB Output is correct
16 Correct 5 ms 8780 KB Output is correct
17 Correct 7 ms 8848 KB Output is correct
18 Correct 8 ms 10000 KB Output is correct
19 Correct 59 ms 13500 KB Output is correct
20 Correct 194 ms 23804 KB Output is correct
21 Correct 425 ms 40300 KB Output is correct
22 Correct 442 ms 40580 KB Output is correct
23 Correct 480 ms 40540 KB Output is correct
24 Correct 430 ms 40708 KB Output is correct
25 Correct 439 ms 40580 KB Output is correct
26 Correct 432 ms 40556 KB Output is correct
27 Correct 429 ms 40364 KB Output is correct
28 Correct 431 ms 40780 KB Output is correct
29 Correct 423 ms 40676 KB Output is correct
30 Correct 431 ms 40584 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 6 ms 8848 KB Output is correct
3 Correct 6 ms 10008 KB Output is correct
4 Correct 48 ms 12276 KB Output is correct
5 Correct 159 ms 18624 KB Output is correct
6 Correct 337 ms 29184 KB Output is correct
7 Correct 329 ms 28960 KB Output is correct
8 Correct 335 ms 29280 KB Output is correct
9 Correct 338 ms 28876 KB Output is correct
10 Correct 322 ms 28864 KB Output is correct
11 Correct 346 ms 28868 KB Output is correct
12 Correct 365 ms 28980 KB Output is correct
13 Correct 337 ms 29212 KB Output is correct
14 Correct 350 ms 29316 KB Output is correct
15 Correct 332 ms 28888 KB Output is correct
16 Correct 5 ms 8780 KB Output is correct
17 Correct 7 ms 8848 KB Output is correct
18 Correct 8 ms 10000 KB Output is correct
19 Correct 59 ms 13500 KB Output is correct
20 Correct 194 ms 23804 KB Output is correct
21 Correct 425 ms 40300 KB Output is correct
22 Correct 442 ms 40580 KB Output is correct
23 Correct 480 ms 40540 KB Output is correct
24 Correct 430 ms 40708 KB Output is correct
25 Correct 439 ms 40580 KB Output is correct
26 Correct 432 ms 40556 KB Output is correct
27 Correct 429 ms 40364 KB Output is correct
28 Correct 431 ms 40780 KB Output is correct
29 Correct 423 ms 40676 KB Output is correct
30 Correct 431 ms 40584 KB Output is correct
31 Correct 5 ms 8848 KB Output is correct
32 Correct 5 ms 8848 KB Output is correct
33 Correct 5 ms 8848 KB Output is correct
34 Correct 7 ms 10128 KB Output is correct
35 Correct 9 ms 10012 KB Output is correct
36 Correct 10 ms 10000 KB Output is correct
37 Correct 89 ms 13284 KB Output is correct
38 Correct 112 ms 12464 KB Output is correct
39 Correct 443 ms 24840 KB Output is correct
40 Correct 1858 ms 107580 KB Output is correct
41 Correct 4418 ms 278364 KB Output is correct
42 Correct 4655 ms 276864 KB Output is correct
43 Correct 4543 ms 279328 KB Output is correct
44 Correct 4581 ms 277356 KB Output is correct
45 Correct 4662 ms 278340 KB Output is correct
46 Correct 4570 ms 276840 KB Output is correct
47 Correct 4506 ms 277568 KB Output is correct
48 Correct 4530 ms 277520 KB Output is correct
49 Correct 4449 ms 277388 KB Output is correct
50 Correct 4401 ms 280176 KB Output is correct
51 Correct 4352 ms 277540 KB Output is correct
52 Correct 4376 ms 277168 KB Output is correct
53 Correct 4285 ms 279276 KB Output is correct
54 Correct 4331 ms 277476 KB Output is correct
55 Correct 4310 ms 277560 KB Output is correct
56 Correct 4307 ms 276176 KB Output is correct
57 Correct 4383 ms 275016 KB Output is correct
58 Correct 4327 ms 279324 KB Output is correct
59 Correct 4292 ms 277400 KB Output is correct
60 Correct 4331 ms 277484 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 5 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct
11 Correct 4 ms 8780 KB Output is correct
12 Correct 6 ms 8848 KB Output is correct
13 Correct 6 ms 10008 KB Output is correct
14 Correct 48 ms 12276 KB Output is correct
15 Correct 159 ms 18624 KB Output is correct
16 Correct 337 ms 29184 KB Output is correct
17 Correct 329 ms 28960 KB Output is correct
18 Correct 335 ms 29280 KB Output is correct
19 Correct 338 ms 28876 KB Output is correct
20 Correct 322 ms 28864 KB Output is correct
21 Correct 346 ms 28868 KB Output is correct
22 Correct 365 ms 28980 KB Output is correct
23 Correct 337 ms 29212 KB Output is correct
24 Correct 350 ms 29316 KB Output is correct
25 Correct 332 ms 28888 KB Output is correct
26 Correct 5 ms 8780 KB Output is correct
27 Correct 7 ms 8848 KB Output is correct
28 Correct 8 ms 10000 KB Output is correct
29 Correct 59 ms 13500 KB Output is correct
30 Correct 194 ms 23804 KB Output is correct
31 Correct 425 ms 40300 KB Output is correct
32 Correct 442 ms 40580 KB Output is correct
33 Correct 480 ms 40540 KB Output is correct
34 Correct 430 ms 40708 KB Output is correct
35 Correct 439 ms 40580 KB Output is correct
36 Correct 432 ms 40556 KB Output is correct
37 Correct 429 ms 40364 KB Output is correct
38 Correct 431 ms 40780 KB Output is correct
39 Correct 423 ms 40676 KB Output is correct
40 Correct 431 ms 40584 KB Output is correct
41 Correct 5 ms 8848 KB Output is correct
42 Correct 5 ms 8848 KB Output is correct
43 Correct 5 ms 8848 KB Output is correct
44 Correct 7 ms 10128 KB Output is correct
45 Correct 9 ms 10012 KB Output is correct
46 Correct 10 ms 10000 KB Output is correct
47 Correct 89 ms 13284 KB Output is correct
48 Correct 112 ms 12464 KB Output is correct
49 Correct 443 ms 24840 KB Output is correct
50 Correct 1858 ms 107580 KB Output is correct
51 Correct 4418 ms 278364 KB Output is correct
52 Correct 4655 ms 276864 KB Output is correct
53 Correct 4543 ms 279328 KB Output is correct
54 Correct 4581 ms 277356 KB Output is correct
55 Correct 4662 ms 278340 KB Output is correct
56 Correct 4570 ms 276840 KB Output is correct
57 Correct 4506 ms 277568 KB Output is correct
58 Correct 4530 ms 277520 KB Output is correct
59 Correct 4449 ms 277388 KB Output is correct
60 Correct 4401 ms 280176 KB Output is correct
61 Correct 4352 ms 277540 KB Output is correct
62 Correct 4376 ms 277168 KB Output is correct
63 Correct 4285 ms 279276 KB Output is correct
64 Correct 4331 ms 277476 KB Output is correct
65 Correct 4310 ms 277560 KB Output is correct
66 Correct 4307 ms 276176 KB Output is correct
67 Correct 4383 ms 275016 KB Output is correct
68 Correct 4327 ms 279324 KB Output is correct
69 Correct 4292 ms 277400 KB Output is correct
70 Correct 4331 ms 277484 KB Output is correct
71 Correct 118 ms 11652 KB Output is correct
72 Correct 117 ms 11636 KB Output is correct
73 Correct 118 ms 11760 KB Output is correct
74 Correct 119 ms 11728 KB Output is correct
75 Correct 118 ms 11620 KB Output is correct
76 Correct 480 ms 16400 KB Output is correct
77 Correct 477 ms 16392 KB Output is correct
78 Correct 472 ms 16264 KB Output is correct
79 Correct 488 ms 16392 KB Output is correct
80 Correct 475 ms 16244 KB Output is correct
81 Correct 1957 ms 36688 KB Output is correct
82 Correct 1963 ms 36476 KB Output is correct
83 Correct 1970 ms 36580 KB Output is correct
84 Correct 1944 ms 36176 KB Output is correct
85 Correct 1990 ms 37944 KB Output is correct
86 Correct 1769 ms 27956 KB Output is correct
87 Correct 1775 ms 28164 KB Output is correct
88 Correct 1773 ms 26660 KB Output is correct
89 Correct 1777 ms 27836 KB Output is correct
90 Correct 1795 ms 27176 KB Output is correct
91 Correct 3121 ms 32096 KB Output is correct
92 Correct 3105 ms 31756 KB Output is correct
93 Correct 3075 ms 31888 KB Output is correct
94 Correct 3076 ms 30844 KB Output is correct
95 Correct 3046 ms 31876 KB Output is correct
96 Correct 2340 ms 28144 KB Output is correct
97 Correct 2348 ms 28348 KB Output is correct
98 Correct 2356 ms 28148 KB Output is correct
99 Correct 2317 ms 28184 KB Output is correct
100 Correct 2321 ms 28168 KB Output is correct
101 Correct 2337 ms 28160 KB Output is correct
102 Correct 2319 ms 27984 KB Output is correct
103 Correct 2380 ms 28424 KB Output is correct
104 Correct 2335 ms 28424 KB Output is correct
105 Correct 2314 ms 28420 KB Output is correct
106 Correct 1895 ms 27884 KB Output is correct
107 Correct 1908 ms 27936 KB Output is correct
108 Correct 1896 ms 28036 KB Output is correct
109 Correct 1906 ms 28200 KB Output is correct
110 Correct 1906 ms 28032 KB Output is correct
111 Correct 1901 ms 27788 KB Output is correct
112 Correct 1874 ms 27652 KB Output is correct
113 Correct 1912 ms 28084 KB Output is correct
114 Correct 1896 ms 28100 KB Output is correct
115 Correct 1925 ms 28092 KB Output is correct

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 5 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 6 ms 8788 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct
11 Correct 4 ms 8780 KB Output is correct
12 Correct 6 ms 8848 KB Output is correct
13 Correct 6 ms 10008 KB Output is correct
14 Correct 48 ms 12276 KB Output is correct
15 Correct 159 ms 18624 KB Output is correct
16 Correct 337 ms 29184 KB Output is correct
17 Correct 329 ms 28960 KB Output is correct
18 Correct 335 ms 29280 KB Output is correct
19 Correct 338 ms 28876 KB Output is correct
20 Correct 322 ms 28864 KB Output is correct
21 Correct 346 ms 28868 KB Output is correct
22 Correct 365 ms 28980 KB Output is correct
23 Correct 337 ms 29212 KB Output is correct
24 Correct 350 ms 29316 KB Output is correct
25 Correct 332 ms 28888 KB Output is correct
26 Correct 5 ms 8780 KB Output is correct
27 Correct 7 ms 8848 KB Output is correct
28 Correct 8 ms 10000 KB Output is correct
29 Correct 59 ms 13500 KB Output is correct
30 Correct 194 ms 23804 KB Output is correct
31 Correct 425 ms 40300 KB Output is correct
32 Correct 442 ms 40580 KB Output is correct
33 Correct 480 ms 40540 KB Output is correct
34 Correct 430 ms 40708 KB Output is correct
35 Correct 439 ms 40580 KB Output is correct
36 Correct 432 ms 40556 KB Output is correct
37 Correct 429 ms 40364 KB Output is correct
38 Correct 431 ms 40780 KB Output is correct
39 Correct 423 ms 40676 KB Output is correct
40 Correct 431 ms 40584 KB Output is correct
41 Correct 5 ms 8848 KB Output is correct
42 Correct 5 ms 8848 KB Output is correct
43 Correct 5 ms 8848 KB Output is correct
44 Correct 7 ms 10128 KB Output is correct
45 Correct 9 ms 10012 KB Output is correct
46 Correct 10 ms 10000 KB Output is correct
47 Correct 89 ms 13284 KB Output is correct
48 Correct 112 ms 12464 KB Output is correct
49 Correct 443 ms 24840 KB Output is correct
50 Correct 1858 ms 107580 KB Output is correct
51 Correct 4418 ms 278364 KB Output is correct
52 Correct 4655 ms 276864 KB Output is correct
53 Correct 4543 ms 279328 KB Output is correct
54 Correct 4581 ms 277356 KB Output is correct
55 Correct 4662 ms 278340 KB Output is correct
56 Correct 4570 ms 276840 KB Output is correct
57 Correct 4506 ms 277568 KB Output is correct
58 Correct 4530 ms 277520 KB Output is correct
59 Correct 4449 ms 277388 KB Output is correct
60 Correct 4401 ms 280176 KB Output is correct
61 Correct 4352 ms 277540 KB Output is correct
62 Correct 4376 ms 277168 KB Output is correct
63 Correct 4285 ms 279276 KB Output is correct
64 Correct 4331 ms 277476 KB Output is correct
65 Correct 4310 ms 277560 KB Output is correct
66 Correct 4307 ms 276176 KB Output is correct
67 Correct 4383 ms 275016 KB Output is correct
68 Correct 4327 ms 279324 KB Output is correct
69 Correct 4292 ms 277400 KB Output is correct
70 Correct 4331 ms 277484 KB Output is correct
71 Correct 118 ms 11652 KB Output is correct
72 Correct 117 ms 11636 KB Output is correct
73 Correct 118 ms 11760 KB Output is correct
74 Correct 119 ms 11728 KB Output is correct
75 Correct 118 ms 11620 KB Output is correct
76 Correct 480 ms 16400 KB Output is correct
77 Correct 477 ms 16392 KB Output is correct
78 Correct 472 ms 16264 KB Output is correct
79 Correct 488 ms 16392 KB Output is correct
80 Correct 475 ms 16244 KB Output is correct
81 Correct 1957 ms 36688 KB Output is correct
82 Correct 1963 ms 36476 KB Output is correct
83 Correct 1970 ms 36580 KB Output is correct
84 Correct 1944 ms 36176 KB Output is correct
85 Correct 1990 ms 37944 KB Output is correct
86 Correct 1769 ms 27956 KB Output is correct
87 Correct 1775 ms 28164 KB Output is correct
88 Correct 1773 ms 26660 KB Output is correct
89 Correct 1777 ms 27836 KB Output is correct
90 Correct 1795 ms 27176 KB Output is correct
91 Correct 3121 ms 32096 KB Output is correct
92 Correct 3105 ms 31756 KB Output is correct
93 Correct 3075 ms 31888 KB Output is correct
94 Correct 3076 ms 30844 KB Output is correct
95 Correct 3046 ms 31876 KB Output is correct
96 Correct 2340 ms 28144 KB Output is correct
97 Correct 2348 ms 28348 KB Output is correct
98 Correct 2356 ms 28148 KB Output is correct
99 Correct 2317 ms 28184 KB Output is correct
100 Correct 2321 ms 28168 KB Output is correct
101 Correct 2337 ms 28160 KB Output is correct
102 Correct 2319 ms 27984 KB Output is correct
103 Correct 2380 ms 28424 KB Output is correct
104 Correct 2335 ms 28424 KB Output is correct
105 Correct 2314 ms 28420 KB Output is correct
106 Correct 1895 ms 27884 KB Output is correct
107 Correct 1908 ms 27936 KB Output is correct
108 Correct 1896 ms 28036 KB Output is correct
109 Correct 1906 ms 28200 KB Output is correct
110 Correct 1906 ms 28032 KB Output is correct
111 Correct 1901 ms 27788 KB Output is correct
112 Correct 1874 ms 27652 KB Output is correct
113 Correct 1912 ms 28084 KB Output is correct
114 Correct 1896 ms 28100 KB Output is correct
115 Correct 1925 ms 28092 KB Output is correct
116 Correct 691 ms 10744 KB Output is correct
117 Correct 1080 ms 11124 KB Output is correct
118 Correct 1421 ms 14132 KB Output is correct
119 Correct 3647 ms 14732 KB Output is correct
120 Correct 4536 ms 13972 KB Output is correct
121 Correct 5436 ms 26760 KB Output is correct
122 Correct 6198 ms 22904 KB Output is correct
123 Execution timed out 7076 ms 110976 KB Time limit exceeded
124 Halted 0 ms 0 KB -