oj.uz

Submission #689583

# Submission time Handle Problem Language Result Execution time Memory
689583 2023-01-28T19:05:46 Z Cyanmond Fish 2 (JOI22_fish2) C++17
100 / 100
 1740 ms 21444 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf64 = 1ll << 50;
constexpr int inf = 1000000000;

template <class M>
class segTree {
    int n, size;
    using T = typename M::T;
    std::vector<T> data;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

  public:
    segTree(int n_) : n(n_) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, M::id());
    }

    void set(int i, T v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    T fold(int l, int r) {
        T pl = M::id(), pr = M::id();
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                pl = M::op(pl, data[l++]);
            }
            if (r % 2 == 1) {
                pr = M::op(data[--r], pr);
            }
        }
        return M::op(pl, pr);
    }

    template <class F>
    int maxRight(int l, F f) {
        assert(f(M::id()));
        if (l == n) {
            return n;
        }

        l += size;
        T p = M::id();
        do {
            while (l % 2 == 0) {
                l /= 2;
            }
            if (not f(M::op(p, data[l]))) {
                while (l < size) {
                    l *= 2;
                    if (f(M::op(p, data[l]))) {
                        p = M::op(p, data[l]);
                        ++l;
                    }
                }
                return l - size;
            }
            p = M::op(p, data[l]);
            ++l;
        } while ((l & (-l)) != l);

        return n;
    }

    template <class F>
    int minLeft(int r, F f) {
        assert(f(M::id()));
        if (r == 0) {
            return 0;
        }

        r += size;
        T p = M::id();
        do {
            --r;
            while (r > 1 and (r % 2 == 1)) {
                r /= 2;
            }
            if (not f(M::op(data[r], p))) {
                while (r < size) {
                    r = 2 * r + 1;
                    if (f(M::op(data[r], p))) {
                        p = M::op(data[r], p);
                        --r;
                    }
                }
                return r + 1 - size;
            }
        } while ((r & (-r)) != r);

        return 0;
    }
};

constexpr int B = 1000;

struct rangeSum64 {
    using T = i64;

    static T op(T a, T b) {
        return a + b;
    }

    static T id() {
        return 0;
    }
};

struct rangeMax64 {
    using T = i64;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return -inf64;
    }
};

struct rangeMaxWithIndex32 {
    using T = std::pair<int, int>;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return {-inf, 0};
    }
};

struct rangeSum32 {
    using T = int;

    static T op(T a, T b) {
        return a + b;
    }

    static T id() {
        return 0;
    }
};

struct rangeMax32 {
    using T = int;

    static T op(T a, T b) {
        return std::max(a, b);
    }

    static T id() {
        return -inf;
    }
};

int main() {
    // input
    int N;
    std::cin >> N;
    std::vector<i64> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }

    segTree<rangeSum64> sumA(N);
    segTree<rangeMax64> maxA(N);
    for (int i = 0; i < N; ++i) {
        sumA.set(i, A[i]);
        maxA.set(i, A[i]);
    }

    segTree<rangeMaxWithIndex32> maxR(N);

    auto expandRange = [&](int &l, int &r) {
        while (true) {
            const auto sum = sumA.fold(l, r);
            const auto limitL = maxA.minLeft(l, [&](const auto v) { return v <= sum; });
            const auto limitR = maxA.maxRight(r, [&](const auto v) { return v <= sum; });
            const auto newL = limitL, newR = limitR;
            if (l == newL and r == newR) {
                break;
            }
            l = newL;
            r = newR;
        }
    };

    auto findRanges = [&](const int m, auto f) {
        int l = m, r = m + 1;

        while (true) {
            expandRange(l, r);
            if (l == 0 and r == N) {
                break;
            }

            f(l, r);
            if (l == 0) {
                ++r;
                continue;
            }
            if (r == N) {
                --l;
                continue;
            }
            if (A[l - 1] < A[r]) {
                --l;
            } else {
                ++r;
            }
        }
    };

    auto eraseRanges = [&](const int m, auto f) {
        while (true) {
            const auto [ma, i] = maxR.fold(0, m + 1);
            if (ma <= m) {
                break;
            }
            f(i, ma);
        }
    };

    std::vector<std::set<int>> rangesEachL(N);
    std::vector<int> countShortRanges(N);
    segTree<rangeSum32> sumPoints(N);
    segTree<rangeMax32> maxLargeRangesR(N);

    for (int i = 0; i < N; ++i) {
        sumPoints.set(i, 1);
    }

    auto addPoint = [&](const int i, const int d) {
        assert(d == 1 or d == -1);
        if (countShortRanges[i] == 0 and d == 1) {
            sumPoints.set(i, 0);
        }
        if (countShortRanges[i] == 1 and d == -1) {
            sumPoints.set(i, 1);
        }
        countShortRanges[i] += d;
        assert(0 <= countShortRanges[i]);
    };

    auto applyAddRange = [&](int l, int r) {
        if (rangesEachL[l].find(r) != rangesEachL[l].end()) {
            return;
        }
        rangesEachL[l].insert(r);
        maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});

        if (r - l < B) {
            for (int i = l; i < r; ++i) {
                addPoint(i, 1);
            }
        } else {
            maxLargeRangesR.set(l, *rangesEachL[l].rbegin());
        }
    };

    auto applyEraseRange = [&](int l, int r) {
        assert(rangesEachL[l].find(r) != rangesEachL[l].end());
        rangesEachL[l].erase(r);
        maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});

        if (r - l < B) {
            for (int i = l; i < r; ++i) {
                addPoint(i, -1);
            }
        } else {
            if (not rangesEachL[l].empty()) {
                const auto v = *rangesEachL[l].rbegin();
                if (v - l >= B) {
                    maxLargeRangesR.set(l, v);
                } else {
                    maxLargeRangesR.set(l, -inf);
                }
            } else {
                maxLargeRangesR.set(l, -inf);
            }
        }
    };

    for (int i = 0; i < N; ++i) {
        findRanges(i, applyAddRange);
    }

    // answer queries
    int Q;
    std::cin >> Q;
    while (Q--) {
        int t;
        std::cin >> t;
        
        if (t == 1) {
            int x;
            i64 y;
            std::cin >> x >> y;
            --x;
            A[x] = y;
            sumA.set(x, y);
            maxA.set(x, y);
            eraseRanges(x, applyEraseRange);
            if (x != 0) {
                eraseRanges(x - 1, applyEraseRange);
            }
            if (x != N - 1) {
                eraseRanges(x + 1, applyEraseRange);
            }
            findRanges(x, applyAddRange);
            if (x != 0) {
                findRanges(x - 1, applyAddRange);
            }
            if (x != N - 1) {
                findRanges(x + 1, applyAddRange);
            }
        }

        if (t == 2) {
            int l, r;
            std::cin >> l >> r;
            --l;

            // find true l and r
            i64 memo = -1;
            int realL = l;
            if (l != 0) {
                memo = A[l - 1];
                A[l - 1] = inf64;
                sumA.set(l - 1, A[l - 1]);
                maxA.set(l - 1, A[l - 1]);
            }
            findRanges(l, [&](int a, int b) {
                assert(a == l);
                if (b < r) {
                    realL = b;
                }
            });
            if (l != 0) {
                A[l - 1] = memo;
                sumA.set(l - 1, A[l - 1]);
                maxA.set(l - 1, A[l - 1]);
            }

            int realR = r;
            if (r != N) {
                memo = A[r];
                A[r] = inf64;
                sumA.set(r, A[r]);
                maxA.set(r, A[r]);
            }
            findRanges(r - 1, [&](int a, int b) {
                assert(b == r);
                if (a > l) {
                    realR = a;
                }
            });
            if (r != N) {
                A[r] = memo;
                sumA.set(r, A[r]);
                maxA.set(r, A[r]);
            }

            assert(realL < realR);

            if (r - l < B) {
                std::vector<int> imos(r - l + 1);
                auto itr = rangesEachL[l].lower_bound(r);
                if (itr != rangesEachL[l].begin()) {
                    --itr;
                    ++imos[0];
                    --imos[*itr - l];
                }
                for (int i = l + 1; i < r; ++i) {
                    if (rangesEachL[i].empty()) {
                        continue;
                    }
                    auto avalR = rangesEachL[i].rbegin();
                    ++imos[i - l];
                    --imos[std::min(r, *avalR) - l];
                }

                int answer = 0;
                for (int i = 0; i < r - l; ++i) {
                    if (realL <= i + l and i + l < realR and imos[i] == 0) {
                        ++answer;
                    }
                    imos[i + 1] += imos[i];
                }

                std::cout << answer << std::endl;
                continue;
            }

            int answer = 0;
            auto itr = rangesEachL[l].lower_bound(r);
            int nowR = realL;
            if (realL == l) {
                if (countShortRanges[l] == 0) {
                    ++answer;
                }
                ++nowR;
            }
            while (nowR < realR) {
                const auto nextR = maxLargeRangesR.fold(l + 1, nowR + 1);
                if (nextR > nowR) {
                    nowR = nextR;
                } else {
                    // problem...
                    const auto nextStep = maxLargeRangesR.maxRight(nowR, [&](const auto v) {
                        return v <= nowR;
                    });
                    answer += sumPoints.fold(nowR, std::min(realR, nextStep));
                    nowR = nextStep;
                }
            }

            std::cout << answer << std::endl;
        }
    }
}

Compilation message

fish2.cpp: In function 'int main()':
fish2.cpp:410:18: warning: variable 'itr' set but not used [-Wunused-but-set-variable]
  410 |             auto itr = rangesEachL[l].lower_bound(r);
      |                  ^~~

Subtask #1
5.0 / 5.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 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 308 KB Output is correct
13 Correct 4 ms 308 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 404 KB Output is correct
18 Correct 3 ms 304 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 179 ms 18920 KB Output is correct
3 Correct 201 ms 18160 KB Output is correct
4 Correct 194 ms 19020 KB Output is correct
5 Correct 212 ms 18208 KB Output is correct
6 Correct 97 ms 17312 KB Output is correct
7 Correct 205 ms 15788 KB Output is correct
8 Correct 106 ms 17444 KB Output is correct
9 Correct 188 ms 15764 KB Output is correct
10 Correct 147 ms 16772 KB Output is correct
11 Correct 194 ms 16488 KB Output is correct
12 Correct 105 ms 16392 KB Output is correct
13 Correct 104 ms 16436 KB Output is correct
14 Correct 96 ms 18160 KB Output is correct
15 Correct 105 ms 18084 KB Output is correct

Subtask #3
12.0 / 12.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 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 308 KB Output is correct
13 Correct 4 ms 308 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 404 KB Output is correct
18 Correct 3 ms 304 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 179 ms 18920 KB Output is correct
23 Correct 201 ms 18160 KB Output is correct
24 Correct 194 ms 19020 KB Output is correct
25 Correct 212 ms 18208 KB Output is correct
26 Correct 97 ms 17312 KB Output is correct
27 Correct 205 ms 15788 KB Output is correct
28 Correct 106 ms 17444 KB Output is correct
29 Correct 188 ms 15764 KB Output is correct
30 Correct 147 ms 16772 KB Output is correct
31 Correct 194 ms 16488 KB Output is correct
32 Correct 105 ms 16392 KB Output is correct
33 Correct 104 ms 16436 KB Output is correct
34 Correct 96 ms 18160 KB Output is correct
35 Correct 105 ms 18084 KB Output is correct
36 Correct 187 ms 19488 KB Output is correct
37 Correct 209 ms 18352 KB Output is correct
38 Correct 200 ms 17856 KB Output is correct
39 Correct 191 ms 19480 KB Output is correct
40 Correct 199 ms 17928 KB Output is correct
41 Correct 102 ms 17440 KB Output is correct
42 Correct 101 ms 17324 KB Output is correct
43 Correct 203 ms 15776 KB Output is correct
44 Correct 195 ms 15776 KB Output is correct
45 Correct 159 ms 17136 KB Output is correct
46 Correct 183 ms 16828 KB Output is correct
47 Correct 215 ms 15532 KB Output is correct
48 Correct 125 ms 16496 KB Output is correct
49 Correct 113 ms 16704 KB Output is correct
50 Correct 103 ms 18124 KB Output is correct
51 Correct 117 ms 18040 KB Output is correct
52 Correct 98 ms 18160 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 179 ms 18920 KB Output is correct
3 Correct 201 ms 18160 KB Output is correct
4 Correct 194 ms 19020 KB Output is correct
5 Correct 212 ms 18208 KB Output is correct
6 Correct 97 ms 17312 KB Output is correct
7 Correct 205 ms 15788 KB Output is correct
8 Correct 106 ms 17444 KB Output is correct
9 Correct 188 ms 15764 KB Output is correct
10 Correct 147 ms 16772 KB Output is correct
11 Correct 194 ms 16488 KB Output is correct
12 Correct 105 ms 16392 KB Output is correct
13 Correct 104 ms 16436 KB Output is correct
14 Correct 96 ms 18160 KB Output is correct
15 Correct 105 ms 18084 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1004 ms 20188 KB Output is correct
18 Correct 634 ms 21292 KB Output is correct
19 Correct 912 ms 20148 KB Output is correct
20 Correct 1085 ms 20140 KB Output is correct
21 Correct 1030 ms 20116 KB Output is correct
22 Correct 619 ms 21444 KB Output is correct
23 Correct 1055 ms 20116 KB Output is correct
24 Correct 1060 ms 20540 KB Output is correct
25 Correct 992 ms 20296 KB Output is correct
26 Correct 998 ms 20456 KB Output is correct
27 Correct 517 ms 19324 KB Output is correct
28 Correct 511 ms 19276 KB Output is correct
29 Correct 511 ms 19252 KB Output is correct
30 Correct 1037 ms 17540 KB Output is correct
31 Correct 1029 ms 17408 KB Output is correct
32 Correct 1324 ms 18436 KB Output is correct
33 Correct 626 ms 18620 KB Output is correct
34 Correct 1335 ms 18012 KB Output is correct
35 Correct 1173 ms 17548 KB Output is correct
36 Correct 691 ms 18776 KB Output is correct
37 Correct 614 ms 18092 KB Output is correct
38 Correct 618 ms 18048 KB Output is correct
39 Correct 521 ms 20016 KB Output is correct
40 Correct 504 ms 19940 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 179 ms 18920 KB Output is correct
3 Correct 201 ms 18160 KB Output is correct
4 Correct 194 ms 19020 KB Output is correct
5 Correct 212 ms 18208 KB Output is correct
6 Correct 97 ms 17312 KB Output is correct
7 Correct 205 ms 15788 KB Output is correct
8 Correct 106 ms 17444 KB Output is correct
9 Correct 188 ms 15764 KB Output is correct
10 Correct 147 ms 16772 KB Output is correct
11 Correct 194 ms 16488 KB Output is correct
12 Correct 105 ms 16392 KB Output is correct
13 Correct 104 ms 16436 KB Output is correct
14 Correct 96 ms 18160 KB Output is correct
15 Correct 105 ms 18084 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1313 ms 20108 KB Output is correct
18 Correct 859 ms 20580 KB Output is correct
19 Correct 1491 ms 19536 KB Output is correct
20 Correct 792 ms 20532 KB Output is correct
21 Correct 1219 ms 20044 KB Output is correct
22 Correct 867 ms 20520 KB Output is correct
23 Correct 1550 ms 19684 KB Output is correct
24 Correct 859 ms 20436 KB Output is correct
25 Correct 1350 ms 19628 KB Output is correct
26 Correct 417 ms 19120 KB Output is correct
27 Correct 478 ms 19164 KB Output is correct
28 Correct 714 ms 19332 KB Output is correct
29 Correct 428 ms 19112 KB Output is correct
30 Correct 466 ms 19324 KB Output is correct
31 Correct 787 ms 19368 KB Output is correct
32 Correct 805 ms 19796 KB Output is correct
33 Correct 883 ms 17860 KB Output is correct
34 Correct 718 ms 20272 KB Output is correct
35 Correct 477 ms 18092 KB Output is correct
36 Correct 759 ms 19376 KB Output is correct
37 Correct 753 ms 19132 KB Output is correct
38 Correct 619 ms 18764 KB Output is correct
39 Correct 457 ms 19776 KB Output is correct
40 Correct 388 ms 19784 KB Output is correct

Subtask #6
17.0 / 17.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 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 308 KB Output is correct
13 Correct 4 ms 308 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 404 KB Output is correct
18 Correct 3 ms 304 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 179 ms 18920 KB Output is correct
23 Correct 201 ms 18160 KB Output is correct
24 Correct 194 ms 19020 KB Output is correct
25 Correct 212 ms 18208 KB Output is correct
26 Correct 97 ms 17312 KB Output is correct
27 Correct 205 ms 15788 KB Output is correct
28 Correct 106 ms 17444 KB Output is correct
29 Correct 188 ms 15764 KB Output is correct
30 Correct 147 ms 16772 KB Output is correct
31 Correct 194 ms 16488 KB Output is correct
32 Correct 105 ms 16392 KB Output is correct
33 Correct 104 ms 16436 KB Output is correct
34 Correct 96 ms 18160 KB Output is correct
35 Correct 105 ms 18084 KB Output is correct
36 Correct 187 ms 19488 KB Output is correct
37 Correct 209 ms 18352 KB Output is correct
38 Correct 200 ms 17856 KB Output is correct
39 Correct 191 ms 19480 KB Output is correct
40 Correct 199 ms 17928 KB Output is correct
41 Correct 102 ms 17440 KB Output is correct
42 Correct 101 ms 17324 KB Output is correct
43 Correct 203 ms 15776 KB Output is correct
44 Correct 195 ms 15776 KB Output is correct
45 Correct 159 ms 17136 KB Output is correct
46 Correct 183 ms 16828 KB Output is correct
47 Correct 215 ms 15532 KB Output is correct
48 Correct 125 ms 16496 KB Output is correct
49 Correct 113 ms 16704 KB Output is correct
50 Correct 103 ms 18124 KB Output is correct
51 Correct 117 ms 18040 KB Output is correct
52 Correct 98 ms 18160 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1004 ms 20188 KB Output is correct
55 Correct 634 ms 21292 KB Output is correct
56 Correct 912 ms 20148 KB Output is correct
57 Correct 1085 ms 20140 KB Output is correct
58 Correct 1030 ms 20116 KB Output is correct
59 Correct 619 ms 21444 KB Output is correct
60 Correct 1055 ms 20116 KB Output is correct
61 Correct 1060 ms 20540 KB Output is correct
62 Correct 992 ms 20296 KB Output is correct
63 Correct 998 ms 20456 KB Output is correct
64 Correct 517 ms 19324 KB Output is correct
65 Correct 511 ms 19276 KB Output is correct
66 Correct 511 ms 19252 KB Output is correct
67 Correct 1037 ms 17540 KB Output is correct
68 Correct 1029 ms 17408 KB Output is correct
69 Correct 1324 ms 18436 KB Output is correct
70 Correct 626 ms 18620 KB Output is correct
71 Correct 1335 ms 18012 KB Output is correct
72 Correct 1173 ms 17548 KB Output is correct
73 Correct 691 ms 18776 KB Output is correct
74 Correct 614 ms 18092 KB Output is correct
75 Correct 618 ms 18048 KB Output is correct
76 Correct 521 ms 20016 KB Output is correct
77 Correct 504 ms 19940 KB Output is correct
78 Correct 0 ms 212 KB Output is correct
79 Correct 1313 ms 20108 KB Output is correct
80 Correct 859 ms 20580 KB Output is correct
81 Correct 1491 ms 19536 KB Output is correct
82 Correct 792 ms 20532 KB Output is correct
83 Correct 1219 ms 20044 KB Output is correct
84 Correct 867 ms 20520 KB Output is correct
85 Correct 1550 ms 19684 KB Output is correct
86 Correct 859 ms 20436 KB Output is correct
87 Correct 1350 ms 19628 KB Output is correct
88 Correct 417 ms 19120 KB Output is correct
89 Correct 478 ms 19164 KB Output is correct
90 Correct 714 ms 19332 KB Output is correct
91 Correct 428 ms 19112 KB Output is correct
92 Correct 466 ms 19324 KB Output is correct
93 Correct 787 ms 19368 KB Output is correct
94 Correct 805 ms 19796 KB Output is correct
95 Correct 883 ms 17860 KB Output is correct
96 Correct 718 ms 20272 KB Output is correct
97 Correct 477 ms 18092 KB Output is correct
98 Correct 759 ms 19376 KB Output is correct
99 Correct 753 ms 19132 KB Output is correct
100 Correct 619 ms 18764 KB Output is correct
101 Correct 457 ms 19776 KB Output is correct
102 Correct 388 ms 19784 KB Output is correct
103 Correct 1551 ms 19156 KB Output is correct
104 Correct 800 ms 21332 KB Output is correct
105 Correct 1080 ms 20180 KB Output is correct
106 Correct 826 ms 20720 KB Output is correct
107 Correct 1740 ms 19436 KB Output is correct
108 Correct 823 ms 21212 KB Output is correct
109 Correct 1318 ms 19896 KB Output is correct
110 Correct 854 ms 20596 KB Output is correct
111 Correct 1092 ms 20252 KB Output is correct
112 Correct 848 ms 20600 KB Output is correct
113 Correct 491 ms 19232 KB Output is correct
114 Correct 543 ms 19408 KB Output is correct
115 Correct 812 ms 19324 KB Output is correct
116 Correct 817 ms 19288 KB Output is correct
117 Correct 523 ms 19360 KB Output is correct
118 Correct 829 ms 18472 KB Output is correct
119 Correct 478 ms 19108 KB Output is correct
120 Correct 815 ms 19368 KB Output is correct
121 Correct 851 ms 19156 KB Output is correct
122 Correct 827 ms 19716 KB Output is correct
123 Correct 982 ms 17508 KB Output is correct
124 Correct 800 ms 19036 KB Output is correct
125 Correct 1110 ms 17412 KB Output is correct
126 Correct 826 ms 18872 KB Output is correct
127 Correct 817 ms 19192 KB Output is correct
128 Correct 713 ms 18520 KB Output is correct
129 Correct 575 ms 19952 KB Output is correct
130 Correct 531 ms 19880 KB Output is correct