oj.uz

Submission #697551

# Submission time Handle Problem Language Result Execution time Memory
697551 2023-02-10T10:40:48 Z piOOE Diversity (CEOI21_diversity) C++17
100 / 100
 6621 ms 14796 KB 
#pragma GCC optimize("O3, unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SmartFenwick {
    vector<ll> k, b;
    int n{};
    ll S = 0, Sum = 0;

    void init(int x) {
        n = x;
        k.resize(x + 1), b.resize(x + 1);
    }

    inline void add(int i, ll v, ll vv) {
        for (int x = i + 1; x <= n; x += x & -x) {
            k[x] += v;
            b[x] += vv;
        }
    }

    inline void rangeAdd(int l, int r, ll v) {
        Sum += (r - l) * v;
        if (l == 0) {
            S += v;
            add(r, -v, (r - 1) * v);
        } else {
            add(l, v, (l - 1) * -v);
        }
    }

    inline ll sum(int i) {
        ll K = 0, B = 0;

        for (int x = i + 1; x > 0; x -= x & -x) {
            K += k[x], B += b[x];
        }

        return B + K * i;
    }

    inline ll rangeSum(int l, int r) {
        return sum(r - 1) - sum(l - 1) + (r - l) * S;
    }
} t[2][2]; // (left/right), (L/R)

struct Query {
    int l, r, block, idx;

    bool operator<(Query oth) const {
        if (oth.block != block) {
            return block < oth.block;
        }

        return (block & 1) ? r > oth.r : r < oth.r;
    }
};

constexpr int B = 1400;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> yy = a;
    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    for (int &x : a) {
        x = lower_bound(yy.begin(), yy.end(), x) - yy.begin();
    }

    const int m = yy.size();

    vector<Query> queries(q);
    vector<ll> answer(q);

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l -= 1;

        queries[i].l = l, queries[i].r = r, queries[i].block = l / B, queries[i].idx = i;
    }

    sort(queries.begin(), queries.end());

    vector<int> head(n + 1);

    for (int i = 1; i <= n; ++i) {
        head[i] = m;
    }

    vector<int> pos(m), cnt(m), ord(m);
    iota(pos.begin(), pos.end(), 0);
    ord = pos;

    int siz[2]{(m + 1) / 2, m / 2};

    t[0][0].init(siz[0]);
    t[0][1].init(siz[0]);
    t[1][0].init(siz[1]);
    t[1][1].init(siz[1]);

    ll ans = 0;

    int len = 0;

    auto eval = [&](int i) {
        return 1LL * cnt[i] * (len - cnt[i]) + 1LL * (cnt[i] + 1) * cnt[i] / 2;
    };

    auto modify = [&](int i, int x) {
        ans += x * len;

        len += x;

        ans -= eval(i);

        int p = pos[i];
        int start = (x == -1 ? head[cnt[i]] : head[cnt[i] + 1] - 1);

        if (p != start) {
            int id = ord[start];
            pos[id] = p;
            ord[p] = id;
            pos[i] = start;
            ord[start] = i;
            p = start;
        }

        int side = p % 2;
        int s = p / 2;

        ans += x * t[side][side ^ 1].rangeSum(s + 1, siz[side]);
        t[side][side].rangeAdd(s + 1, siz[side], x);

        t[side][side ^ 1].rangeAdd(0, s, x);
        ans += x * t[side][side].rangeSum(0, s);

        ans += x * t[side ^ 1][side ^ 1].Sum;
        t[side ^ 1][side].S += x;
        t[side ^ 1][side].Sum += x * siz[side ^ 1];

        if (x == -1) {
            head[cnt[i]] = p + 1;
            cnt[i] -= 1;
        } else {
            cnt[i] += 1;
            head[cnt[i]] = p;
        }

        ans += eval(i);
    };

    int lx = 0, rx = 0;

    for (auto [l, r, bl, i] : queries) {
        while (rx < r) {
            modify(a[rx++], 1);
        }

        while (lx > l) {
            modify(a[--lx], 1);
        }

        while (lx < l) {
            modify(a[lx++], -1);
        }

        while (rx > r) {
            modify(a[--rx], -1);
        }

        answer[i] = ans;
    }

    for (int i = 0; i < q; ++i) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Compilation message

diversity.cpp:1:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops")
      |                                        ^
diversity.cpp:13:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   13 |     void init(int x) {
      |                    ^
diversity.cpp:18:39: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   18 |     inline void add(int i, ll v, ll vv) {
      |                                       ^
diversity.cpp:25:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   25 |     inline void rangeAdd(int l, int r, ll v) {
      |                                            ^
diversity.cpp:35:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   35 |     inline ll sum(int i) {
      |                        ^
diversity.cpp:45:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   45 |     inline ll rangeSum(int l, int r) {
      |                                    ^
diversity.cpp:53:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   53 |     bool operator<(Query oth) const {
      |                               ^~~~~
diversity.cpp:64:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 | int main() {
      |          ^
diversity.cpp: In function 'int main()':
diversity.cpp:121:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  121 |     auto eval = [&](int i) {
      |                          ^
diversity.cpp:125:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  125 |     auto modify = [&](int i, int x) {
      |                                   ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 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 1 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 17 ms 1492 KB Output is correct
5 Correct 28 ms 2668 KB Output is correct
6 Correct 41 ms 3816 KB Output is correct
7 Correct 40 ms 3840 KB Output is correct
8 Correct 49 ms 3824 KB Output is correct
9 Correct 51 ms 3820 KB Output is correct
10 Correct 47 ms 3796 KB Output is correct
11 Correct 45 ms 3792 KB Output is correct
12 Correct 54 ms 3832 KB Output is correct
13 Correct 41 ms 3804 KB Output is correct
14 Correct 40 ms 3796 KB Output is correct
15 Correct 41 ms 3836 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 17 ms 1492 KB Output is correct
5 Correct 28 ms 2668 KB Output is correct
6 Correct 41 ms 3816 KB Output is correct
7 Correct 40 ms 3840 KB Output is correct
8 Correct 49 ms 3824 KB Output is correct
9 Correct 51 ms 3820 KB Output is correct
10 Correct 47 ms 3796 KB Output is correct
11 Correct 45 ms 3792 KB Output is correct
12 Correct 54 ms 3832 KB Output is correct
13 Correct 41 ms 3804 KB Output is correct
14 Correct 40 ms 3796 KB Output is correct
15 Correct 41 ms 3836 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 20 ms 1508 KB Output is correct
20 Correct 32 ms 2656 KB Output is correct
21 Correct 47 ms 3820 KB Output is correct
22 Correct 50 ms 3916 KB Output is correct
23 Correct 52 ms 3808 KB Output is correct
24 Correct 48 ms 3828 KB Output is correct
25 Correct 55 ms 3812 KB Output is correct
26 Correct 49 ms 3840 KB Output is correct
27 Correct 48 ms 3804 KB Output is correct
28 Correct 54 ms 3788 KB Output is correct
29 Correct 54 ms 3804 KB Output is correct
30 Correct 51 ms 3796 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 17 ms 1492 KB Output is correct
5 Correct 28 ms 2668 KB Output is correct
6 Correct 41 ms 3816 KB Output is correct
7 Correct 40 ms 3840 KB Output is correct
8 Correct 49 ms 3824 KB Output is correct
9 Correct 51 ms 3820 KB Output is correct
10 Correct 47 ms 3796 KB Output is correct
11 Correct 45 ms 3792 KB Output is correct
12 Correct 54 ms 3832 KB Output is correct
13 Correct 41 ms 3804 KB Output is correct
14 Correct 40 ms 3796 KB Output is correct
15 Correct 41 ms 3836 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 20 ms 1508 KB Output is correct
20 Correct 32 ms 2656 KB Output is correct
21 Correct 47 ms 3820 KB Output is correct
22 Correct 50 ms 3916 KB Output is correct
23 Correct 52 ms 3808 KB Output is correct
24 Correct 48 ms 3828 KB Output is correct
25 Correct 55 ms 3812 KB Output is correct
26 Correct 49 ms 3840 KB Output is correct
27 Correct 48 ms 3804 KB Output is correct
28 Correct 54 ms 3788 KB Output is correct
29 Correct 54 ms 3804 KB Output is correct
30 Correct 51 ms 3796 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 3 ms 340 KB Output is correct
35 Correct 3 ms 400 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 12 ms 856 KB Output is correct
38 Correct 12 ms 852 KB Output is correct
39 Correct 23 ms 1496 KB Output is correct
40 Correct 47 ms 2712 KB Output is correct
41 Correct 72 ms 3876 KB Output is correct
42 Correct 78 ms 3876 KB Output is correct
43 Correct 75 ms 3788 KB Output is correct
44 Correct 69 ms 3880 KB Output is correct
45 Correct 77 ms 3876 KB Output is correct
46 Correct 70 ms 3816 KB Output is correct
47 Correct 70 ms 3968 KB Output is correct
48 Correct 72 ms 3812 KB Output is correct
49 Correct 89 ms 3820 KB Output is correct
50 Correct 80 ms 3824 KB Output is correct
51 Correct 70 ms 3808 KB Output is correct
52 Correct 76 ms 3824 KB Output is correct
53 Correct 87 ms 3804 KB Output is correct
54 Correct 83 ms 3812 KB Output is correct
55 Correct 69 ms 3828 KB Output is correct
56 Correct 77 ms 3804 KB Output is correct
57 Correct 68 ms 3804 KB Output is correct
58 Correct 69 ms 3876 KB Output is correct
59 Correct 73 ms 3872 KB Output is correct
60 Correct 72 ms 3816 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 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 1 ms 256 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 17 ms 1492 KB Output is correct
15 Correct 28 ms 2668 KB Output is correct
16 Correct 41 ms 3816 KB Output is correct
17 Correct 40 ms 3840 KB Output is correct
18 Correct 49 ms 3824 KB Output is correct
19 Correct 51 ms 3820 KB Output is correct
20 Correct 47 ms 3796 KB Output is correct
21 Correct 45 ms 3792 KB Output is correct
22 Correct 54 ms 3832 KB Output is correct
23 Correct 41 ms 3804 KB Output is correct
24 Correct 40 ms 3796 KB Output is correct
25 Correct 41 ms 3836 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 20 ms 1508 KB Output is correct
30 Correct 32 ms 2656 KB Output is correct
31 Correct 47 ms 3820 KB Output is correct
32 Correct 50 ms 3916 KB Output is correct
33 Correct 52 ms 3808 KB Output is correct
34 Correct 48 ms 3828 KB Output is correct
35 Correct 55 ms 3812 KB Output is correct
36 Correct 49 ms 3840 KB Output is correct
37 Correct 48 ms 3804 KB Output is correct
38 Correct 54 ms 3788 KB Output is correct
39 Correct 54 ms 3804 KB Output is correct
40 Correct 51 ms 3796 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 340 KB Output is correct
45 Correct 3 ms 400 KB Output is correct
46 Correct 3 ms 468 KB Output is correct
47 Correct 12 ms 856 KB Output is correct
48 Correct 12 ms 852 KB Output is correct
49 Correct 23 ms 1496 KB Output is correct
50 Correct 47 ms 2712 KB Output is correct
51 Correct 72 ms 3876 KB Output is correct
52 Correct 78 ms 3876 KB Output is correct
53 Correct 75 ms 3788 KB Output is correct
54 Correct 69 ms 3880 KB Output is correct
55 Correct 77 ms 3876 KB Output is correct
56 Correct 70 ms 3816 KB Output is correct
57 Correct 70 ms 3968 KB Output is correct
58 Correct 72 ms 3812 KB Output is correct
59 Correct 89 ms 3820 KB Output is correct
60 Correct 80 ms 3824 KB Output is correct
61 Correct 70 ms 3808 KB Output is correct
62 Correct 76 ms 3824 KB Output is correct
63 Correct 87 ms 3804 KB Output is correct
64 Correct 83 ms 3812 KB Output is correct
65 Correct 69 ms 3828 KB Output is correct
66 Correct 77 ms 3804 KB Output is correct
67 Correct 68 ms 3804 KB Output is correct
68 Correct 69 ms 3876 KB Output is correct
69 Correct 73 ms 3872 KB Output is correct
70 Correct 72 ms 3816 KB Output is correct
71 Correct 16 ms 980 KB Output is correct
72 Correct 14 ms 980 KB Output is correct
73 Correct 17 ms 980 KB Output is correct
74 Correct 15 ms 984 KB Output is correct
75 Correct 14 ms 984 KB Output is correct
76 Correct 28 ms 1616 KB Output is correct
77 Correct 28 ms 1628 KB Output is correct
78 Correct 27 ms 1760 KB Output is correct
79 Correct 29 ms 1624 KB Output is correct
80 Correct 32 ms 1700 KB Output is correct
81 Correct 60 ms 3032 KB Output is correct
82 Correct 59 ms 3040 KB Output is correct
83 Correct 63 ms 3048 KB Output is correct
84 Correct 58 ms 3100 KB Output is correct
85 Correct 68 ms 3044 KB Output is correct
86 Correct 82 ms 3424 KB Output is correct
87 Correct 67 ms 3420 KB Output is correct
88 Correct 65 ms 3436 KB Output is correct
89 Correct 68 ms 3532 KB Output is correct
90 Correct 64 ms 3424 KB Output is correct
91 Correct 141 ms 8024 KB Output is correct
92 Correct 143 ms 8040 KB Output is correct
93 Correct 129 ms 8160 KB Output is correct
94 Correct 158 ms 8028 KB Output is correct
95 Correct 136 ms 8168 KB Output is correct
96 Correct 159 ms 12516 KB Output is correct
97 Correct 172 ms 12476 KB Output is correct
98 Correct 161 ms 12512 KB Output is correct
99 Correct 167 ms 12580 KB Output is correct
100 Correct 165 ms 12476 KB Output is correct
101 Correct 177 ms 12364 KB Output is correct
102 Correct 152 ms 12476 KB Output is correct
103 Correct 165 ms 12472 KB Output is correct
104 Correct 164 ms 12472 KB Output is correct
105 Correct 160 ms 12476 KB Output is correct
106 Correct 168 ms 14544 KB Output is correct
107 Correct 150 ms 14796 KB Output is correct
108 Correct 160 ms 14696 KB Output is correct
109 Correct 159 ms 14552 KB Output is correct
110 Correct 152 ms 14756 KB Output is correct
111 Correct 151 ms 14660 KB Output is correct
112 Correct 161 ms 14636 KB Output is correct
113 Correct 149 ms 14652 KB Output is correct
114 Correct 151 ms 14564 KB Output is correct
115 Correct 183 ms 14540 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 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 1 ms 256 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 17 ms 1492 KB Output is correct
15 Correct 28 ms 2668 KB Output is correct
16 Correct 41 ms 3816 KB Output is correct
17 Correct 40 ms 3840 KB Output is correct
18 Correct 49 ms 3824 KB Output is correct
19 Correct 51 ms 3820 KB Output is correct
20 Correct 47 ms 3796 KB Output is correct
21 Correct 45 ms 3792 KB Output is correct
22 Correct 54 ms 3832 KB Output is correct
23 Correct 41 ms 3804 KB Output is correct
24 Correct 40 ms 3796 KB Output is correct
25 Correct 41 ms 3836 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 20 ms 1508 KB Output is correct
30 Correct 32 ms 2656 KB Output is correct
31 Correct 47 ms 3820 KB Output is correct
32 Correct 50 ms 3916 KB Output is correct
33 Correct 52 ms 3808 KB Output is correct
34 Correct 48 ms 3828 KB Output is correct
35 Correct 55 ms 3812 KB Output is correct
36 Correct 49 ms 3840 KB Output is correct
37 Correct 48 ms 3804 KB Output is correct
38 Correct 54 ms 3788 KB Output is correct
39 Correct 54 ms 3804 KB Output is correct
40 Correct 51 ms 3796 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 340 KB Output is correct
45 Correct 3 ms 400 KB Output is correct
46 Correct 3 ms 468 KB Output is correct
47 Correct 12 ms 856 KB Output is correct
48 Correct 12 ms 852 KB Output is correct
49 Correct 23 ms 1496 KB Output is correct
50 Correct 47 ms 2712 KB Output is correct
51 Correct 72 ms 3876 KB Output is correct
52 Correct 78 ms 3876 KB Output is correct
53 Correct 75 ms 3788 KB Output is correct
54 Correct 69 ms 3880 KB Output is correct
55 Correct 77 ms 3876 KB Output is correct
56 Correct 70 ms 3816 KB Output is correct
57 Correct 70 ms 3968 KB Output is correct
58 Correct 72 ms 3812 KB Output is correct
59 Correct 89 ms 3820 KB Output is correct
60 Correct 80 ms 3824 KB Output is correct
61 Correct 70 ms 3808 KB Output is correct
62 Correct 76 ms 3824 KB Output is correct
63 Correct 87 ms 3804 KB Output is correct
64 Correct 83 ms 3812 KB Output is correct
65 Correct 69 ms 3828 KB Output is correct
66 Correct 77 ms 3804 KB Output is correct
67 Correct 68 ms 3804 KB Output is correct
68 Correct 69 ms 3876 KB Output is correct
69 Correct 73 ms 3872 KB Output is correct
70 Correct 72 ms 3816 KB Output is correct
71 Correct 16 ms 980 KB Output is correct
72 Correct 14 ms 980 KB Output is correct
73 Correct 17 ms 980 KB Output is correct
74 Correct 15 ms 984 KB Output is correct
75 Correct 14 ms 984 KB Output is correct
76 Correct 28 ms 1616 KB Output is correct
77 Correct 28 ms 1628 KB Output is correct
78 Correct 27 ms 1760 KB Output is correct
79 Correct 29 ms 1624 KB Output is correct
80 Correct 32 ms 1700 KB Output is correct
81 Correct 60 ms 3032 KB Output is correct
82 Correct 59 ms 3040 KB Output is correct
83 Correct 63 ms 3048 KB Output is correct
84 Correct 58 ms 3100 KB Output is correct
85 Correct 68 ms 3044 KB Output is correct
86 Correct 82 ms 3424 KB Output is correct
87 Correct 67 ms 3420 KB Output is correct
88 Correct 65 ms 3436 KB Output is correct
89 Correct 68 ms 3532 KB Output is correct
90 Correct 64 ms 3424 KB Output is correct
91 Correct 141 ms 8024 KB Output is correct
92 Correct 143 ms 8040 KB Output is correct
93 Correct 129 ms 8160 KB Output is correct
94 Correct 158 ms 8028 KB Output is correct
95 Correct 136 ms 8168 KB Output is correct
96 Correct 159 ms 12516 KB Output is correct
97 Correct 172 ms 12476 KB Output is correct
98 Correct 161 ms 12512 KB Output is correct
99 Correct 167 ms 12580 KB Output is correct
100 Correct 165 ms 12476 KB Output is correct
101 Correct 177 ms 12364 KB Output is correct
102 Correct 152 ms 12476 KB Output is correct
103 Correct 165 ms 12472 KB Output is correct
104 Correct 164 ms 12472 KB Output is correct
105 Correct 160 ms 12476 KB Output is correct
106 Correct 168 ms 14544 KB Output is correct
107 Correct 150 ms 14796 KB Output is correct
108 Correct 160 ms 14696 KB Output is correct
109 Correct 159 ms 14552 KB Output is correct
110 Correct 152 ms 14756 KB Output is correct
111 Correct 151 ms 14660 KB Output is correct
112 Correct 161 ms 14636 KB Output is correct
113 Correct 149 ms 14652 KB Output is correct
114 Correct 151 ms 14564 KB Output is correct
115 Correct 183 ms 14540 KB Output is correct
116 Correct 1122 ms 1996 KB Output is correct
117 Correct 1193 ms 2000 KB Output is correct
118 Correct 1298 ms 2596 KB Output is correct
119 Correct 1633 ms 2608 KB Output is correct
120 Correct 1710 ms 2636 KB Output is correct
121 Correct 1881 ms 3224 KB Output is correct
122 Correct 2037 ms 3268 KB Output is correct
123 Correct 2683 ms 4532 KB Output is correct
124 Correct 3150 ms 4724 KB Output is correct
125 Correct 3196 ms 4916 KB Output is correct
126 Correct 3436 ms 5532 KB Output is correct
127 Correct 3464 ms 5540 KB Output is correct
128 Correct 3406 ms 5536 KB Output is correct
129 Correct 3415 ms 5532 KB Output is correct
130 Correct 3506 ms 5580 KB Output is correct
131 Correct 3565 ms 5672 KB Output is correct
132 Correct 3500 ms 5708 KB Output is correct
133 Correct 3487 ms 5672 KB Output is correct
134 Correct 3449 ms 5672 KB Output is correct
135 Correct 3435 ms 5708 KB Output is correct
136 Correct 3445 ms 5668 KB Output is correct
137 Correct 3497 ms 5676 KB Output is correct
138 Correct 3480 ms 5684 KB Output is correct
139 Correct 3493 ms 5672 KB Output is correct
140 Correct 3445 ms 5672 KB Output is correct
141 Correct 3854 ms 5696 KB Output is correct
142 Correct 3835 ms 5696 KB Output is correct
143 Correct 3803 ms 5700 KB Output is correct
144 Correct 3834 ms 5700 KB Output is correct
145 Correct 3820 ms 5696 KB Output is correct
146 Correct 4407 ms 5872 KB Output is correct
147 Correct 4359 ms 5868 KB Output is correct
148 Correct 4424 ms 5884 KB Output is correct
149 Correct 4428 ms 5872 KB Output is correct
150 Correct 4431 ms 5868 KB Output is correct
151 Correct 4660 ms 6084 KB Output is correct
152 Correct 4667 ms 6084 KB Output is correct
153 Correct 4660 ms 6128 KB Output is correct
154 Correct 4717 ms 6080 KB Output is correct
155 Correct 4664 ms 6080 KB Output is correct
156 Correct 6309 ms 7908 KB Output is correct
157 Correct 6333 ms 7880 KB Output is correct
158 Correct 6473 ms 7856 KB Output is correct
159 Correct 6343 ms 10216 KB Output is correct
160 Correct 6621 ms 10224 KB Output is correct
161 Correct 4773 ms 9404 KB Output is correct
162 Correct 4746 ms 9508 KB Output is correct
163 Correct 4783 ms 9400 KB Output is correct
164 Correct 4759 ms 9400 KB Output is correct
165 Correct 4807 ms 9404 KB Output is correct
166 Correct 3524 ms 7944 KB Output is correct
167 Correct 3584 ms 7940 KB Output is correct
168 Correct 3580 ms 7944 KB Output is correct
169 Correct 3535 ms 7880 KB Output is correct
170 Correct 3589 ms 7944 KB Output is correct
171 Correct 3273 ms 7892 KB Output is correct
172 Correct 3286 ms 7864 KB Output is correct
173 Correct 3302 ms 7860 KB Output is correct
174 Correct 3321 ms 7856 KB Output is correct
175 Correct 3311 ms 7864 KB Output is correct