Submission #753057

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
753057	2023-06-04T14:02:34 Z	I_love_Hoang_Yen	Sequence (APIO23_sequence)	C++17	47 / 100	2000 ms	61512 KB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
#define SZ(s) ((int) ((s).size()))
using namespace std;
 
bool is_sub_3(const std::vector<int> a) {
    auto mit = max_element(a.begin(), a.end());
    return std::is_sorted(a.begin(), mit)
        && std::is_sorted(mit, a.end(), std::greater<int>());
}
 
int len(const std::pair<int,int>& p) {
    return p.second - p.first + 1;
}
bool can_be_median(int cnt_less, int cnt_equal, int cnt_greater) {
    return cnt_equal + cnt_less >= cnt_greater;
}
 
int sub3(const vector<int>& a) {
    int n = SZ(a);
    unordered_map<int, vector<pair<int,int>>> pos;
    int l = 0;
    while (l < n) {
        int r = l;
        while (r < n && a[l] == a[r]) ++r;
        pos[a[l]].emplace_back(l, r-1);
        l = r;
    }
    int res = 0;
    for (const auto& [val, lrs] : pos) {
        // only 1 segment
        for (const auto& lr : lrs) res = max(res, len(lr));
 
        // 2 segments
        if (SZ(lrs) < 2) continue;
        assert(SZ(lrs) == 2);
        int cnt_equal = len(lrs[0]) + len(lrs[1]);
        int cnt_greater = len({lrs[0].second + 1, lrs[1].first - 1});
        int cnt_less = len({0, lrs[0].first - 1}) + len({lrs[1].second + 1, n-1});
        if (can_be_median(cnt_less, cnt_equal, cnt_greater)) {
            res = max(res, cnt_equal);
        }
    }
    return res;
}
 
// SegTree, copied from AtCoder library {{{
// AtCoder doc: https://atcoder.github.io/ac-library/master/document_en/segtree.html
//
// Notes:
// - Index of elements from 0 -> n-1
// - Range queries are [l, r-1]
//
// Tested:
// - (binary search) https://atcoder.jp/contests/practice2/tasks/practice2_j
// - https://oj.vnoi.info/problem/gss
// - https://oj.vnoi.info/problem/nklineup
// - (max_right & min_left for delete position queries) https://oj.vnoi.info/problem/segtree_itstr
// - https://judge.yosupo.jp/problem/point_add_range_sum
// - https://judge.yosupo.jp/problem/point_set_range_composite
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
 
template<
    class T,  // data type for nodes
    T (*op) (T, T),  // operator to combine 2 nodes
    T (*e)() // identity element
>
struct SegTree {
    SegTree() : SegTree(0) {}
    explicit SegTree(int n) : SegTree(vector<T> (n, e())) {}
    explicit SegTree(const vector<T>& v) : _n((int) v.size()) {
        log = ceil_pow2(_n);
        size = 1<<log;
        d = vector<T> (2*size, e());
 
        for (int i = 0; i < _n; i++) d[size+i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
 
    // 0 <= p < n
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
 
    // 0 <= p < n
    T get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
 
    // Get product in range [l, r-1]
    // 0 <= l <= r <= n
    // For empty segment (l == r) -> return e()
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        T sml = e(), smr = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
 
    T all_prod() const {
        return d[1];
    }
 
    // Binary search on SegTree to find largest r:
    //    f(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
    //    f(op(a[l] .. a[r])) = false    (assuming op(..., a[n]), which is out of bound, is always false)
    template <bool (*f)(T)> int max_right(int l) const {
        return max_right(l, [](T x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        T sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
 
    // Binary search on SegTree to find smallest l:
    //    f(op(a[l] .. a[r-1])) = true      (assuming empty array is always true)
    //    f(op(a[l-1] .. a[r-1])) = false   (assuming op(a[-1], ..), which is out of bound, is always false)
    template <bool (*f)(T)> int min_left(int r) const {
        return min_left(r, [](T x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        T sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
 
private:
    int _n, size, log;
    vector<T> d;
 
    void update(int k) {
        d[k] = op(d[2*k], d[2*k+1]);
    }
};
// }}}
// SegTree examples {{{
// Examples: Commonly used SegTree ops: max / min / sum
struct MaxSegTreeOp {
    static int op(int x, int y) {
        return max(x, y);
    }
    static int e() {
        return INT_MIN;
    }
};
 
struct MinSegTreeOp {
    static int op(int x, int y) {
        return min(x, y);
    }
    static int e() {
        return INT_MAX;
    }
};
 
struct SumSegTreeOp {
    static long long op(long long x, long long y) {
        return x + y;
    }
    static long long e() {
        return 0;
    }
};
 
// using STMax = SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e>;
// using STMin = SegTree<int, MinSegTreeOp::op, MinSegTreeOp::e>;
// using STSum = SegTree<int, SumSegTreeOp::op, SumSegTreeOp::e>;
// }}}
// Lazy Segment Tree, copied from AtCoder {{{
// Source: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
// Doc: https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html
//
// Notes:
// - Index of elements from 0
// - Range queries are [l, r-1]
// - composition(f, g) should return f(g())
//
// Tested:
// - https://oj.vnoi.info/problem/qmax2
// - https://oj.vnoi.info/problem/lites
// - (range set, add, mult, sum) https://oj.vnoi.info/problem/segtree_itmix
// - (range add (i-L)*A + B, sum) https://oj.vnoi.info/problem/segtree_itladder
// - https://atcoder.jp/contests/practice2/tasks/practice2_l
// - https://judge.yosupo.jp/problem/range_affine_range_sum

template<
    class S,                 // node data type
    S (*op) (S, S),          // combine 2 nodes
    S (*e) (),               // identity element
    class F,                 // lazy propagation tag
    S (*mapping) (F, S),     // apply tag F on a node
    F (*composition) (F, F), // combine 2 tags
    F (*id)()                // identity tag
>
struct LazySegTree {
    LazySegTree() : LazySegTree(0) {}
    explicit LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {}
    explicit LazySegTree(const vector<S>& v) : _n((int) v.size()) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    // 0 <= p < n
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    // 0 <= p < n
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    // Get product in range [l, r-1]
    // 0 <= l <= r <= n
    // For empty segment (l == r) -> return e()
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() {
        return d[1];
    }

    // 0 <= p < n
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    // Apply f on all elements in range [l, r-1]
    // 0 <= l <= r <= n
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    // Binary search on SegTree to find largest r:
    //    f(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
    //    f(op(a[l] .. a[r])) = false    (assuming op(..., a[n]), which is out of bound, is always false)
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // Binary search on SegTree to find smallest l:
    //    f(op(a[l] .. a[r-1])) = true      (assuming empty array is always true)
    //    f(op(a[l-1] .. a[r-1])) = false   (assuming op(a[-1], ..), which is out of bound, is always false)
    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }


private:
    int _n, size, log;
    vector<S> d;
    vector<F> lz;

    void update(int k) {
        d[k] = op(d[2*k], d[2*k+1]);
    }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2*k, lz[k]);
        all_apply(2*k+1, lz[k]);
        lz[k] = id();
    }
};
// }}}
 
int sub4(int n, const std::vector<int>& a) {
    int res = 0;
    int ln = *max_element(a.begin(), a.end());
    for (int median = 0; median <= ln; ++median) {
        vector<int> cnt_less(n, 0);
        vector<int> cnt_equal(n, 0);
        vector<int> cnt_greater(n, 0);
        for (int i = 0; i < n; ++i) {
            cnt_less[i] = a[i] < median;
            cnt_equal[i] = a[i] == median;
            cnt_greater[i] = a[i] > median;
        }
        std::partial_sum(cnt_less.begin(), cnt_less.end(), cnt_less.begin());
        std::partial_sum(cnt_equal.begin(), cnt_equal.end(), cnt_equal.begin());
        std::partial_sum(cnt_greater.begin(), cnt_greater.end(), cnt_greater.begin());
 
        //    cnt_less[r]   + cnt_equal[r]   - cnt_greater[r]
        // >= cnt_less[l-1] + cnt_equal[l-1] - cnt_greater[l-1]
        //
        //    cnt_less[r]   - cnt_equal[r]   - cnt_greater[r]
        //  < cnt_less[l-1] - cnt_equal[l-1] - cnt_greater[l-1]
        //
        //  l < r
        vector<vector<pair<int,int>>> f1_at(n*2 + 1);
        for (int i = n-1; i >= 0; --i) {
            // add n so that everything >= 0
            int f1 = cnt_less[i] + cnt_equal[i] - cnt_greater[i] + n;
            int f2 = cnt_less[i] - cnt_equal[i] - cnt_greater[i] + n;
            f1_at[f1].emplace_back(i, f2);
        }
        f1_at[n].emplace_back(-1, n);
 
        SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e> st(2*n + 1);
        for (int f1 = 2*n; f1 >= 0; --f1) {
            // f1(r) >= f1(l-1) && f2(r) < f2(l-1)
            for (const auto& [i, f2] : f1_at[f1]) {
                // l = i + 1
                int max_r = st.prod(0, f2 + 1);
                if (max_r > i) {
                    res = max(res, cnt_equal[max_r] - (i >= 0 ? cnt_equal[i] : 0));
                }
                // r = i
                st.set(f2, max(st.get(f2), i));
            }
        }
    }
    return res;
}

using F = int;
int mapping(F f, int s) {
    return f + s;
}
F composition(F f, F g) {
    return f + g;
}
F id() { return 0; }

bool can(int n, int eq, const vector<int>& a, const vector<vector<int>>& ids) {
    int ln = *max_element(a.begin(), a.end());
    LazySegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e, F, mapping, composition, id> st_max(n + 1);
    LazySegTree<int, MinSegTreeOp::op, MinSegTreeOp::e, F, mapping, composition, id> st_min(n + 1);
    st_max.set(0, 0);
    st_min.set(0, 0);
 
    for (int median = 0; median <= ln; median++) {
        if (median == 0) {
            for (int i = 1; i <= n; ++i) {
                st_max.set(i, i);
                st_min.set(i, i);
            }
        } else {
            // greater is affected?
            for (int i : ids[median]) {
                // previously: greater = 1, now: greater = 0
                st_max.apply(i, n+1, -1);
                st_min.apply(i, n+1, -1);
            }
            // less is affected?
            for (int i : ids[median-1]) {
                // previously: less = 0, now: less = 1
                st_max.apply(i, n+1, -1);
                st_min.apply(i, n+1, -1);
            }
        }
 
        if (SZ(ids[median]) < eq) continue;
        for (int ix = 0, iy = eq-1; iy < SZ(ids[median]); ++ix, ++iy) {
            int x = ids[median][ix];
            int y = ids[median][iy];
 
            // find [l, r]:
            // - l <= x < y <= r
            // - less + eq >= greater
            // - greater + eq >= less
            // - eq >= greater - less >= -eq
            // - eq >= (greater(r) - less(r)) - (greater(l-1) - less(l-1)) >= -eq
 
            int max_val = st_max.prod(y, n+1) - st_min.prod(0, x);
            int min_val = st_min.prod(y, n+1) - st_max.prod(0, x);
 
            // [-eq, eq] and [min_val, max_val] intersects
            if (min_val <= eq && max_val >= -eq) return true;
        }
    }
    return false;
}

int sub5(int n, std::vector<int> a) {
    // ids from 1
    a.insert(a.begin(), 0);
 
    vector<vector<int>> ids(n + 1);
    for (int i = 1; i <= n; ++i) {
        ids[a[i]].push_back(i);
    }
 
    int max_freq = 0;
    for (int i = 1; i <= n; ++i) {
        max_freq = max(max_freq, SZ(ids[i]));
    }
    int left = 1, right = max_freq, res = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (can(n, mid, a, ids)) {
            res = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}
 
int sequence(int n, std::vector<int> a) {
    if (is_sub_3(a)) return sub3(a);
    return sub4(n, a);
}

Subtask #1

11.0 / 11.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	0 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 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	2 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct

Subtask #2

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	0 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 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	2 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	514 ms	520 KB	Output is correct
14	Correct	523 ms	516 KB	Output is correct
15	Correct	14 ms	468 KB	Output is correct
16	Correct	12 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	505 ms	532 KB	Output is correct
20	Correct	512 ms	468 KB	Output is correct
21	Correct	488 ms	528 KB	Output is correct
22	Correct	498 ms	716 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	145 ms	31724 KB	Output is correct
3	Correct	171 ms	31664 KB	Output is correct
4	Correct	45 ms	6088 KB	Output is correct
5	Correct	168 ms	29196 KB	Output is correct
6	Correct	150 ms	29096 KB	Output is correct
7	Correct	39 ms	6088 KB	Output is correct
8	Correct	38 ms	6092 KB	Output is correct
9	Correct	37 ms	6096 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	427 ms	61384 KB	Output is correct
3	Correct	417 ms	61340 KB	Output is correct
4	Correct	450 ms	61268 KB	Output is correct
5	Correct	425 ms	61428 KB	Output is correct
6	Correct	367 ms	61356 KB	Output is correct

Subtask #5

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2077 ms	61512 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 22.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	0 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 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	2 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	514 ms	520 KB	Output is correct
14	Correct	523 ms	516 KB	Output is correct
15	Correct	14 ms	468 KB	Output is correct
16	Correct	12 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	505 ms	532 KB	Output is correct
20	Correct	512 ms	468 KB	Output is correct
21	Correct	488 ms	528 KB	Output is correct
22	Correct	498 ms	716 KB	Output is correct
23	Execution timed out	2052 ms	11012 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 18.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	0 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 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	2 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	514 ms	520 KB	Output is correct
14	Correct	523 ms	516 KB	Output is correct
15	Correct	14 ms	468 KB	Output is correct
16	Correct	12 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	505 ms	532 KB	Output is correct
20	Correct	512 ms	468 KB	Output is correct
21	Correct	488 ms	528 KB	Output is correct
22	Correct	498 ms	716 KB	Output is correct
23	Correct	145 ms	31724 KB	Output is correct
24	Correct	171 ms	31664 KB	Output is correct
25	Correct	45 ms	6088 KB	Output is correct
26	Correct	168 ms	29196 KB	Output is correct
27	Correct	150 ms	29096 KB	Output is correct
28	Correct	39 ms	6088 KB	Output is correct
29	Correct	38 ms	6092 KB	Output is correct
30	Correct	37 ms	6096 KB	Output is correct
31	Correct	427 ms	61384 KB	Output is correct
32	Correct	417 ms	61340 KB	Output is correct
33	Correct	450 ms	61268 KB	Output is correct
34	Correct	425 ms	61428 KB	Output is correct
35	Correct	367 ms	61356 KB	Output is correct
36	Execution timed out	2077 ms	61512 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-