oj.uz

Submission #1080023

# Submission time Handle Problem Language Result Execution time Memory
1080023 2024-08-29T06:24:16 Z CDuong Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1103 ms 129212 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
    static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
    int n, size, log;
    vector<T> data;
    vector<U> data_action;
    F1 TT; // monoid operation (always adjacent)
    T T_id; // monoid identity
    F2 UU; // monoid operation (superset, subset)
    U U_id; // monoid identity
    F3 UT; // action of U on T (superset, subset)
    // O(n)
    segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
    segment_tree_base &operator=(const segment_tree_base &seg){
        n = seg.n;
        size = seg.size;
        log = seg.log;
        data = seg.data;
        data_action = seg.data_action;
    }
    // O(1)
    friend void swap(segment_tree_base &x, segment_tree_base &y){
        swap(x.n, y.n);
        swap(x.size, y.size);
        swap(x.log, y.log);
        swap(x.data, y.data);
        swap(x.data_action, y.data_action);
    }
    // O(n)
    void build(int n){
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        ifQ data.assign(size << 1, T_id);
        ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
    }
    // O(n)
    void build(int n, T x){
        static_assert(HAS_QUERY);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        fill(data.begin() + size, data.begin() + size + n, x);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    template<class V>
    void build(const vector<V> &a){
        static_assert(HAS_QUERY);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        copy(a.begin(), a.end(), data.begin() + size);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    void build_action(int n){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        build(n);
    }
    // O(n)
    void build_action(int n, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        fill(data_action.begin() + size, data_action.begin() + size + n, f);
    }
    // O(n)
    template<class V>
    void build_action(const vector<V> &a){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        copy(a.begin(), a.end(), data_action.begin() + size);
    }
    // O(1)
    void refresh(int u){
        static_assert(HAS_QUERY);
        data[u] = TT(data[u << 1], data[u << 1 | 1]);
    }
    // O(1)
    void apply(int u, U f){
        static_assert(HAS_UPDATE);
        ifQ data[u] = UT(f, data[u]);
        if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
    }
    // O(1)
    void push(int u){
        static_assert(HAS_UPDATE);
        apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
        data_action[u] = U_id;
    }
    // O(log(n)) if HAS_UPDATE, O(1) otherwise.
    T query(int p){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data[p];
    }
    // O(log(n))
    U query_action(int p){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data_action[p];
    }
    // O(log(n))
    T query(int ql, int qr){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return T_id;
        ql += size, qr += size;
        ifU for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        T res_left = T_id, res_right = T_id;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) res_left = TT(res_left, data[ql ++]);
            if(qr & 1) res_right = TT(data[-- qr], res_right);
        }
        return TT(res_left, res_right);
    }
    // O(1)
    T query_all() const{
        static_assert(HAS_QUERY);
        return data[1];
    }
    // O(n)
    vector<T> to_array(){
        static_assert(HAS_QUERY);
        ifU for(auto u = 1; u < size; ++ u) push(u);
        return vector<T>(data.begin() + size, data.begin() + size + n);
    }
    // O(n)
    vector<U> to_array_of_updates(){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        for(auto u = 1; u < size; ++ u) push(u);
        return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
    }
    // O(log(n))
    void set(int p, T x){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        data[p] = x;
        for(auto i = 1; i <= log; ++ i) refresh(p >> i);
    }
    // O(log(n))
    void set_action(int p, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        data_action[p] = f;
    }
    // O(log(n))
    void update(int p, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        ifQ{
            data[p] = UT(f, data[p]);
            for(auto i = 1; i <= log; ++ i) refresh(p >> i);
        }
        else data_action[p] = UU(f, data_action[p]);
    }
    // O(log(n))
    void update(int ql, int qr, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) apply(ql ++, f);
            if(qr & 1) apply(-- qr, f);
        }
        ql = _ql, qr = _qr;
        ifQ for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
        static_assert(HAS_QUERY && HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        auto recurse = [&](auto self, int u)->void{
            if(exit_rule(data[u])) return;
            if(enter_rule(data[u])){
                apply(u, update_rule(data[u]));
                return;
            }
            push(u);
            self(self, u << 1), self(self, u << 1 | 1);
            refresh(u);
        };
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) recurse(recurse, ql ++);
            if(qr & 1) recurse(recurse, -- qr);
        }
        ql = _ql, qr = _qr;
        for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
    // Returns max r with T
    // O(log(n))
    int max_pref(int ql, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= n && pred(T_id));
        if(ql == n) return n;
        ql += size;
        ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
        T sum = T_id;
        do{
            while(~ql & 1) ql >>= 1;
            if(!pred(TT(sum, data[ql]))){
                while(ql < size){
                    ifU push(ql);
                    ql = ql << 1;
                    if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
                }
                return ql - size;
            }
            sum = TT(sum, data[ql]);
            ++ ql;
        }while((ql & -ql) != ql);
        return n;
    }
    // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
    // Returns min l with T
    // O(log(n))
    int min_suff(int qr, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= qr && qr <= n && pred(T_id));
        if(qr == 0) return 0;
        qr += size;
        ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
        T sum = T_id;
        do{
            -- qr;
            while(qr > 1 && qr & 1) qr >>= 1;
            if(!pred(TT(data[qr], sum))){
                while(qr < size){
                    ifU push(qr);
                    qr = qr << 1 | 1;
                    if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
                }
                return qr + 1 - size;
            }
            sum = TT(data[qr], sum);
        }while((qr & -qr) != qr);
        return 0;
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
        out << "{";
        for(auto i = 0; i < seg.n; ++ i){
            ifQ out << seg.query(i);
            else out << seg.query_action(i);
            if(i != seg.n - 1) out << ", ";
        }
        return out << '}';
    }
#undef ifQ
#undef ifU
};

// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
    using U = int;
    auto _UU = [&](U, U)->U{ return U{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
    using T = int;
    auto _TT = [&](T, T)->T{ return T{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
    return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}

template<class T, class F>
struct sparse_table{
#ifdef LOCAL
    #define ASSERT(x) assert(x)
#else
    #define ASSERT(x) 42
#endif
    int n;
    vector<vector<T>> data;
    F TT;
    T T_id;
    sparse_table(F TT, T T_id): TT(TT), T_id(T_id){ }
    sparse_table &operator=(const sparse_table &st){
        n = st.n;
        data = st.data;
        return *this;
    }
    friend void swap(sparse_table &stl, sparse_table &str){
        swap(stl.n, str.n);
        swap(stl.data, str.data);
    }
    // O(n * log(n))
    void build(const vector<T> &a){
        n = (int)a.size();
        data.assign({a});
        for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
            data.emplace_back(n - (p << 1) + 1);
            for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = TT(data[i - 1][j], data[i - 1][j + p]);
        }
    }
    // O(1)
    T query(int l, int r) const{
        ASSERT(0 <= l && l <= r && r <= n);
        if(l == r) return T_id;
        int d = __lg(r - l);
        return TT(data[d][l], data[d][r - (1 << d)]);
    }
#undef ASSERT
};
template<class T, class F>
auto make_sparse_table(F TT, T T_id){
    return sparse_table(TT, T_id);
}
template<class T>
auto make_rminq(T inf = numeric_limits<T>::max()){
    return sparse_table([&](const T &x, const T &y){ return min(x, y); }, inf);
}
template<class T>
auto make_rmaxq(T minf = numeric_limits<T>::min()){
    return sparse_table([&](const T &x, const T &y){ return max(x, y); }, minf);
}

struct T1 {
    int l, r;
};

T1 TT(const T1 &A, const T1 &B) {
    return T1{min(A.l, B.l), max(A.r, B.r)};
}

void solve() {
    int n;
    cin >> n;

    vector<int> C(n - 1);
    for (auto &val : C) cin >> val;

    vector<vector<int>> B;
    for (int i = 0; i < n; ++i) {
        int sz; cin >> sz;
        B.emplace_back(sz);
        for (auto &val : B.back()) cin >> val;
    }

    vector<int> en(n);
    vector<int> neededl(n - 1, -1);
    {
        map<int, int> mp;
        for (int i = 0; i < n - 1; ++i) {
            for (auto val : B[i]) mp[val] = i;
            neededl[i] = mp.count(C[i]) ? mp[C[i]] : -1;
        }
        for (int i = n - 1; i >= 0; --i) {
            int cur = i;
            while (cur < n - 1) {
                if (neededl[cur] < i) break;
                cur = en[cur + 1];
            }
            en[i] = cur;
            // cout << i << " " << en[i] << endl;
        }
        // cout << endl;
    }
    vector<int> st(n);
    vector<int> neededr(n - 1, -1);
    {
        map<int, int> mp;
        for (int i = n - 2; i >= 0; --i) {
            for (auto val : B[i + 1]) mp[val] = i + 1;
            neededr[i] = mp.count(C[i]) ? mp[C[i]] : n;
            // cout << i << " " << neededr[i] << endl;
        }
        for (int i = 0; i < n; ++i) {
            int cur = i;
            while (cur > 0) {
                if (neededr[cur - 1] > i) break;
                cur = st[cur - 1];
            }
            st[i] = cur;
            // cout << i << " " << cur << endl;
        }
        // cout << endl;
    }

    auto str = make_Q_segment_tree(TT, T1{n, -1});
    str.build(n);

    auto sptr = make_rmaxq<int>();
    sptr.build(neededr);
    auto sptl = make_rminq<int>();
    sptl.build(neededl);

    for (int i = 0; i < n; ++i) {
        int cl = i, cr = i;
        while (1) {
            int ccl = cl, ccr = cr;
            {
                int lo = 0, hi = cl - 1, opt = cl;
                while (lo <= hi) {
                    int mid = (lo + hi) >> 1;
                    if (sptr.query(mid, cl) <= cr) {
                        opt = mid;
                        hi = mid - 1;
                    }
                    else {
                        lo = mid + 1;
                    }
                }
                auto val = str.query(opt, cl);
                cl = min(cl, val.l), cr = max(cr, val.r);
                // cl = opt;
                // assert(opt == st[i]);
            }
            {
                int lo = cr + 1, hi = n - 1, opt = cr;
                while (lo <= hi) {
                    int mid = (lo + hi) >> 1;
                    if (sptl.query(cr, mid) >= cl) {
                        opt = mid;
                        lo = mid + 1;
                    }
                    else {
                        hi = mid - 1;
                    }
                }
                cr = opt;
                // cout << i << " " << opt << " " << en[i] << endl;
                // assert(opt == en[i]);
            }
            if (ccl == cl and ccr == cr) break;
        }
        // cout << i << " " << cl << " " << cr << endl;

        // int l = 0, r = i - 1, opt = i;
        // while (l <= r) {
        //     int mid = (l + r) >> 1;
        //     if (sptr.query(mid, i) <= en[i]) {
        //         opt = mid;
        //         r = mid - 1;
        //     }
        //     else {
        //         l = mid + 1;
        //     }
        // }
        // cout << i << " " << opt << endl;
        // auto val = st.query(opt, i);
        // val.l = min(val.l, i);
        // val.r = max(val.r, en[i]);
        // cout << i << " " << val.l << " " << val.r << endl;
        str.set(i, T1{cl, cr});
        // cout << endl;
    }

    int q; cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x, --y;

        auto val = str.query(x);
        cout << (min(x, y) >= val.l and max(x, y) <= val.r ? "YES" : "NO") << endl;
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Compilation message

long_mansion.cpp:225:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                       ^~~~
long_mansion.cpp:225:55: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                       ^~~~
long_mansion.cpp:225:72: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                        ^~~~
long_mansion.cpp:258:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  258 |     int max_pref(int ql, auto pred){
      |                          ^~~~
long_mansion.cpp:283:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  283 |     int min_suff(int qr, auto pred){
      |                          ^~~~
long_mansion.cpp: In instantiation of 'T sparse_table<T, F>::query(int, int) const [with T = int; F = make_rmaxq<int>::<lambda(const int&, const int&)>]':
long_mansion.cpp:471:43:   required from here
long_mansion.cpp:346:23: warning: statement has no effect [-Wunused-value]
  346 |     #define ASSERT(x) 42
      |                       ^~
long_mansion.cpp:373:9: note: in expansion of macro 'ASSERT'
  373 |         ASSERT(0 <= l && l <= r && r <= n);
      |         ^~~~~~
long_mansion.cpp: In instantiation of 'T sparse_table<T, F>::query(int, int) const [with T = int; F = make_rminq<int>::<lambda(const int&, const int&)>]':
long_mansion.cpp:488:43:   required from here
long_mansion.cpp:346:23: warning: statement has no effect [-Wunused-value]
  346 |     #define ASSERT(x) 42
      |                       ^~
long_mansion.cpp:373:9: note: in expansion of macro 'ASSERT'
  373 |         ASSERT(0 <= l && l <= r && r <= n);
      |         ^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 9 ms 1412 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 591 ms 6484 KB Output is correct
9 Correct 578 ms 6456 KB Output is correct
10 Correct 604 ms 7028 KB Output is correct
11 Correct 578 ms 7880 KB Output is correct
12 Correct 579 ms 6096 KB Output is correct
13 Correct 558 ms 6740 KB Output is correct
14 Correct 596 ms 6720 KB Output is correct
15 Correct 550 ms 6864 KB Output is correct
16 Correct 553 ms 6600 KB Output is correct
17 Correct 550 ms 6720 KB Output is correct
18 Correct 582 ms 6860 KB Output is correct
19 Correct 583 ms 7100 KB Output is correct
20 Correct 545 ms 6644 KB Output is correct
21 Correct 558 ms 6768 KB Output is correct
22 Correct 555 ms 6780 KB Output is correct
23 Correct 568 ms 6480 KB Output is correct
24 Correct 543 ms 6432 KB Output is correct
25 Correct 571 ms 6508 KB Output is correct
26 Correct 546 ms 6496 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 31748 KB Output is correct
2 Correct 717 ms 31172 KB Output is correct
3 Correct 655 ms 30852 KB Output is correct
4 Correct 676 ms 31484 KB Output is correct
5 Correct 636 ms 31236 KB Output is correct
6 Correct 618 ms 30972 KB Output is correct
7 Correct 607 ms 30208 KB Output is correct
8 Correct 610 ms 30464 KB Output is correct
9 Correct 602 ms 30208 KB Output is correct
10 Correct 615 ms 30568 KB Output is correct
11 Correct 597 ms 30208 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 9 ms 1412 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 591 ms 6484 KB Output is correct
9 Correct 578 ms 6456 KB Output is correct
10 Correct 604 ms 7028 KB Output is correct
11 Correct 578 ms 7880 KB Output is correct
12 Correct 579 ms 6096 KB Output is correct
13 Correct 558 ms 6740 KB Output is correct
14 Correct 596 ms 6720 KB Output is correct
15 Correct 550 ms 6864 KB Output is correct
16 Correct 553 ms 6600 KB Output is correct
17 Correct 550 ms 6720 KB Output is correct
18 Correct 582 ms 6860 KB Output is correct
19 Correct 583 ms 7100 KB Output is correct
20 Correct 545 ms 6644 KB Output is correct
21 Correct 558 ms 6768 KB Output is correct
22 Correct 555 ms 6780 KB Output is correct
23 Correct 568 ms 6480 KB Output is correct
24 Correct 543 ms 6432 KB Output is correct
25 Correct 571 ms 6508 KB Output is correct
26 Correct 546 ms 6496 KB Output is correct
27 Correct 663 ms 31748 KB Output is correct
28 Correct 717 ms 31172 KB Output is correct
29 Correct 655 ms 30852 KB Output is correct
30 Correct 676 ms 31484 KB Output is correct
31 Correct 636 ms 31236 KB Output is correct
32 Correct 618 ms 30972 KB Output is correct
33 Correct 607 ms 30208 KB Output is correct
34 Correct 610 ms 30464 KB Output is correct
35 Correct 602 ms 30208 KB Output is correct
36 Correct 615 ms 30568 KB Output is correct
37 Correct 597 ms 30208 KB Output is correct
38 Correct 989 ms 108708 KB Output is correct
39 Correct 1008 ms 129212 KB Output is correct
40 Correct 843 ms 83948 KB Output is correct
41 Correct 876 ms 127472 KB Output is correct
42 Correct 689 ms 32056 KB Output is correct
43 Correct 714 ms 32252 KB Output is correct
44 Correct 879 ms 58220 KB Output is correct
45 Correct 905 ms 58852 KB Output is correct
46 Correct 887 ms 59568 KB Output is correct
47 Correct 771 ms 31860 KB Output is correct
48 Correct 706 ms 31620 KB Output is correct
49 Correct 968 ms 59476 KB Output is correct
50 Correct 941 ms 58980 KB Output is correct
51 Correct 953 ms 58824 KB Output is correct
52 Correct 872 ms 57076 KB Output is correct
53 Correct 1103 ms 85100 KB Output is correct
54 Correct 1028 ms 108648 KB Output is correct
55 Correct 962 ms 85960 KB Output is correct