Submission #672647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672647	2022-12-17T07:45:32 Z	Forested	I want to be the very best too! (NOI17_pokemonmaster)	C++17	100 / 100	956 ms	148716 KB

pokemonmaster

#ifndef LOCAL
#define FAST_IO
#endif

// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
// ============

#ifdef DEBUGF
#else
#define DBG(x) (void)0
#endif

// ============

#include <limits>
#include <utility>

template <typename T>
struct Add {
    using Value = T;
    static Value id() {
        return T(0);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs + rhs;
    }
    static Value inv(const Value &x) {
        return -x;
    }
};

template <typename T>
struct Mul {
    using Value = T;
    static Value id() {
        return Value(1);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs * rhs;
    }
    static Value inv(const Value &x) {
        return Value(1) / x;
    }
};

template <typename T>
struct Min {
    using Value = T;
    static Value id() {
        return std::numeric_limits<T>::max();
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::min(lhs, rhs);
    }
};

template <typename T>
struct Max {
    using Value = T;
    static Value id() {
        return std::numeric_limits<Value>::min();
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::max(lhs, rhs);
    }
};

template <typename T>
struct Xor {
    using Value = T;
    static Value id() {
        return T(0);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs ^ rhs;
    }
    static Value inv(const Value &x) {
        return x;
    }
};

template <typename Monoid>
struct Reversible {
    using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;
    static Value id() {
        return Value(Monoid::id(), Monoid::id());
    }
    static Value op(const Value &v1, const Value &v2) {
        return Value(
            Monoid::op(v1.first, v2.first),
            Monoid::op(v2.second, v1.second));
    }
};

// ============
// ============

#include <cassert>

template <typename Monoid>
class SparseSegmentTree {
public:
    using Value = typename Monoid::Value;
    using Index = long long;
    
private:
    struct Node {
        Node *lft;
        Node *rgt;
        Value prod;
        
        Node(Value v) : lft(nullptr), rgt(nullptr), prod(v) {}
        
#ifdef LOCAL
        ~Node() {
            if (lft) {
                delete lft;
            }
            if (rgt) {
                delete rgt;
            }
        }
#endif
        
        void update_prod() {
            if (!lft && !rgt) {
                prod = Monoid::id();
            } else if (!lft) {
                prod = rgt->prod;
            } else if (!rgt) {
                prod = lft->prod;
            } else {
                prod = Monoid::op(lft->prod, rgt->prod);
            }
        }
    };
    
    static Node *update(Node *cur, Index curl, Index curr, Index upd, Value v) {
        if (!cur) {
            cur = new Node(Monoid::id());
        }
        if (curr - curl == 1) {
            cur->prod = v;
        } else {
            Index curm = (curl + curr) / 2;
            if (upd < curm) {
                cur->lft = update(cur->lft, curl, curm, upd, v);
            } else {
                cur->rgt = update(cur->rgt, curm, curr, upd, v);
            }
            cur->update_prod();
        }
        return cur;
    }
    
    static Value prod(Node *cur, Index curl, Index curr, Index qryl, Index qryr) {
        if (!cur || curr <= qryl || qryr <= curl) {
            return Monoid::id();
        }
        if (qryl <= curl && curr <= qryr) {
            return cur->prod;
        }
        Index curm = (curl + curr) / 2;
        Value pl = prod(cur->lft, curl, curm, qryl, qryr);
        Value pr = prod(cur->rgt, curm, curr, qryl, qryr);
        return Monoid::op(pl, pr);
    }
    
    Index lft;
    Index rgt;
    Node *root;
    
public:
    SparseSegmentTree() : lft(0), rgt(1), root(nullptr) {}
    SparseSegmentTree(Index n) : lft(0), rgt(n), root(nullptr) {
        assert(n > 0);
    }
    SparseSegmentTree(Index l, Index r) : lft(l), rgt(r), root(nullptr) {
        assert(l < r);
    }
    
    void update(Index idx, Value v) {
        root = update(root, lft, rgt, idx, v);
    }
    
    Value prod(Index l, Index r) const {
        return prod(root, lft, rgt, l, r);
    }
};
// ============
// ============

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

class HeavyLightDecomposition {
    std::vector<int> siz;
    std::vector<int> par;
    std::vector<int> hea;
    std::vector<int> in;
    std::vector<int> out;
    std::vector<int> dep;
    std::vector<int> rev;

    template <typename G>
    void dfs1(G &g, int v) {
        if (!g[v].empty() && (int) g[v][0] == par[v]) {
            std::swap(g[v][0], g[v].back());
        }
        for (auto &e : g[v]) {
            int u = (int)e;
            if (u != par[v]) {
                par[u] = v;
                dfs1(g, u);
                siz[v] += siz[u];
                if (siz[u] > siz[(int) g[v][0]]) {
                    std::swap(g[v][0], e);
                }
            }
        }
    }

    template <typename G>
    void dfs2(const G &g, int v, int &time) {
        in[v] = time;
        rev[time++] = v;
        for (auto &e : g[v]) {
            int u = (int)e;
            if (u == par[v]) {
                continue;
            }
            if (u == (int) g[v][0]) {
                hea[u] = hea[v];
            } else {
                hea[u] = u;
            }
            dep[u] = dep[v] + 1;
            dfs2(g, u, time);
        }
        out[v] = time;
    }

public:
    template <typename G>
    HeavyLightDecomposition(G &g, int root = 0) :
        siz(g.size(), 1),
        par(g.size(), root),
        hea(g.size(), root),
        in(g.size(), 0),
        out(g.size(), 0),
        dep(g.size(), 0),
        rev(g.size(), 0) {
        assert(root >= 0 && root < (int) g.size());
        dfs1(g, root);
        int time = 0;
        dfs2(g, root, time);
    }

    int subtree_size(int v) const {
        assert(v >= 0 && v < (int) siz.size());
        return siz[v];
    }

    int parent(int v) const {
        assert(v >= 0 && v < (int) par.size());
        return par[v];
    }

    int in_time(int v) const {
        assert(v >= 0 && v < (int) in.size());
        return in[v];
    }

    int out_time(int v) const {
        assert(v >= 0 && v < (int) out.size());
        return out[v];
    }

    int depth(int v) const {
        assert(v >= 0 && v < (int) dep.size());
        return dep[v];
    }

    int time_to_vertex(int t) const {
        assert(t >= 0 && t < (int) rev.size());
        return rev[t];
    }
    
    int la(int v, int k) const {
        assert(v >= 0 && v < (int) dep.size());
        assert(k >= 0);
        if (k > dep[v]) {
            return -1;
        }
        while (true) {
            int u = hea[v];
            if (in[u] + k <= in[v]) {
                return rev[in[v] - k];
            }
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
        return 0;
    }
    
    int forward(int v, int dst) const {
        assert(v >= 0 && v < (int) dep.size());
        assert(dst >= 0 && dst < (int) dep.size());
        assert(v != dst);
        int l = lca(v, dst);
        if (l == v) {
            return la(dst, dist(v, dst) - 1);
        } else {
            return par[v];
        }
    }

    int lca(int u, int v) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        while (u != v) {
            if (in[u] > in[v]) {
                std::swap(u, v);
            }
            if (hea[u] == hea[v]) {
                v = u;
            } else {
                v = par[hea[v]];
            }
        }
        return u;
    }

    int dist(int u, int v) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    std::vector<std::pair<int, int>> path(int u, int v, bool edge) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        std::vector<std::pair<int, int>> fromu, fromv;
        bool rev = false;
        while (true) {
            if (u == v && edge) {
                break;
            }
            if (in[u] > in[v]) {
                std::swap(u, v);
                std::swap(fromu, fromv);
                rev ^= true;
            }
            if (hea[u] == hea[v]) {
                fromv.emplace_back(in[v], in[u] + (int)edge);
                v = u;
                break;
            } else {
                fromv.emplace_back(in[v], in[hea[v]]);
                v = par[hea[v]];
            }
        }
        if (rev) {
            std::swap(fromu, fromv);
        }
        std::reverse(fromv.begin(), fromv.end());
        fromu.reserve(fromv.size());
        for (auto [x, y] : fromv) {
            fromu.emplace_back(y, x);
        }
        return fromu;
    }
    
    int jump(int u, int v, int k) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        assert(k >= 0);
        int l = lca(u, v);
        int dis = dep[u] + dep[v] - 2 * dep[l];
        if (k > dis) {
            return -1;
        }
        if (k <= dep[u] - dep[l]) {
            return la(u, k);
        } else {
            return la(v, dis - k);
        }
    }
    
    int meet(int u, int v, int w) const {
        return lca(u, v) ^ lca(v, w) ^ lca(w, u);
    }
};

// ============

struct Converted {
    i32 n;
    Vec<Vec<i32>> tree;
    i32 rt;
    Vec<i32> a;
    i32 q;
    Vec<tuple<i32, i32, i32>> queries;  // (0, v, x) or (1, v, -1) or (1, n, -1)
};

Converted convert(i32 r, i32 c, i32 q, const Vec<Vec<i32>> &l,
                  const Vec<Vec<i32>> &p,
                  const Vec<tuple<i32, i32, i32, i32>> &queries) {
    Vec<i32> par(r * c, -1);
    auto find_root = [&](const auto &find_root, i32 v) -> i32 {
        if (par[v] == -1) {
            return v;
        } else {
            return par[v] = find_root(find_root, par[v]);
        }
    };
    Vec<pair<i32, i32>> events;
    REP(i, q) {
        auto [ty, x, y, val] = queries[i];
        if (ty == 1) {
            events.emplace_back(val, r * c + i);
        }
    }
    REP(i, r) REP(j, c) { events.emplace_back(l[i][j], i * c + j); }
    sort(ALL(events));
    const i32 dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    Vec<Vec<i32>> tree(r * c);
    Vec<tuple<i32, i32, i32>> qs(q, make_tuple(0, 0, 0));
    for (auto [_, i] : events) {
        if (i < r * c) {
            i32 x = i / c;
            i32 y = i - x * c;
            REP(dir, 4) {
                i32 tx = x + dx[dir], ty = y + dy[dir];
                if (tx >= 0 && tx < r && ty >= 0 && ty < c &&
                    l[x][y] > l[tx][ty]) {
                    i32 tr = find_root(find_root, tx * c + ty);
                    if (tr != x * c + y) {
                        par[tr] = x * c + y;
                        tree[x * c + y].emplace_back(tr);
                        tree[tr].emplace_back(x * c + y);
                    }
                }
            }
        } else {
            i -= r * c;
            auto [_ty, x, y, val] = queries[i];
            if (val < l[x][y]) {
                qs[i] = make_tuple(1, r * c, -1);
            } else {
                i32 rt = find_root(find_root, x * c + y);
                qs[i] = make_tuple(1, rt, -1);
            }
        }
    }
    REP(i, q) {
        auto [ty, x, y, val] = queries[i];
        if (ty == 0) {
            qs[i] = make_tuple(0, x * c + y, val);
        }
    }
    i32 mx_x = -1, mx_y = -1, mx = -1;
    REP(i, r) REP(j, c) {
        if (chmax(mx, l[i][j])) {
            mx_x = i;
            mx_y = j;
        }
    }
    Vec<i32> a;
    a.reserve(r * c);
    REP(i, r) REP(j, c) { a.push_back(p[i][j]); }
    return Converted{r * c, tree, mx_x * c + mx_y, a, q, qs};
}

Vec<i32> solve(Converted prob) {
    HeavyLightDecomposition hld(prob.tree, prob.rt);
    i32 k = 0;
    REP(i, prob.n) { chmax(k, prob.a[i]); }
    for (auto [ty, x, y] : prob.queries) {
        if (ty == 0) {
            chmax(k, y);
        }
    }
    ++k;
    Vec<SparseSegmentTree<Add<i32>>> segs;
    segs.reserve(k);
    REP(i, k) { segs.emplace_back(SparseSegmentTree<Add<i32>>(prob.n + 1)); }
    SparseSegmentTree<Add<i32>> siz(prob.n + 1);
    auto add = [&](i32 v, i32 x) -> void {
        for (auto [l, r] : hld.path(prob.rt, v, false)) {
            ++r;
            segs[x].update(l, segs[x].prod(l, l + 1) + 1);
            segs[x].update(r, segs[x].prod(r, r + 1) - 1);
        }
        i32 dep = hld.depth(v);
        i32 ok = -1, ng = dep + 1;
        while (ng - ok > 1) {
            i32 mid = (ok + ng) / 2;
            i32 u = hld.la(v, mid);
            if (segs[x].prod(0, hld.in_time(u) + 1) == 1) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        if (ok != -1) {
            i32 u = hld.la(v, ok);
            for (auto [l, r] : hld.path(u, v, false)) {
                ++r;
                siz.update(l, siz.prod(l, l + 1) + 1);
                siz.update(r, siz.prod(r, r + 1) - 1);
            }
        }
    };
    auto sub = [&](i32 v, i32 x) -> void {
        for (auto [l, r] : hld.path(prob.rt, v, false)) {
            ++r;
            segs[x].update(l, segs[x].prod(l, l + 1) - 1);
            segs[x].update(r, segs[x].prod(r, r + 1) + 1);
        }
        i32 dep = hld.depth(v);
        i32 ok = -1, ng = dep + 1;
        while (ng - ok > 1) {
            i32 mid = (ok + ng) / 2;
            i32 u = hld.la(v, mid);
            if (segs[x].prod(0, hld.in_time(u) + 1) == 0) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        if (ok != -1) {
            i32 u = hld.la(v, ok);
            for (auto [l, r] : hld.path(u, v, false)) {
                ++r;
                siz.update(l, siz.prod(l, l + 1) - 1);
                siz.update(r, siz.prod(r, r + 1) + 1);
            }
        }
    };
    REP(v, prob.n) { add(v, prob.a[v]); }
    Vec<i32> ans;
    for (auto [ty, x, y] : prob.queries) {
        if (ty == 0) {
            sub(x, prob.a[x]);
            prob.a[x] = y;
            add(x, prob.a[x]);
        } else {
            if (x == prob.n) {
                ans.push_back(0);
            } else {
                x = hld.in_time(x);
                ans.push_back(siz.prod(0, x + 1));
            }
        }
    }
    return ans;
}

int main() {
    i32 r, c, q;
    cin >> r >> c >> q;
    Vec<Vec<i32>> l(r, Vec<i32>(c));
    REP(i, r) REP(j, c) { cin >> l[i][j]; }
    Vec<Vec<i32>> p(r, Vec<i32>(c));
    REP(i, r) REP(j, c) { cin >> p[i][j]; }
    Vec<i32> dis;
    dis.reserve(r * c);
    REP(i, r) REP(j, c) { dis.push_back(l[i][j]); }
    sort(ALL(dis));
    REP(i, dis.size() - 1) { assert(dis[i] != dis[i + 1]); }
    Vec<tuple<i32, i32, i32, i32>> queries(q);
    for (auto &[ty, x, y, val] : queries) {
        cin >> ty >> y >> x >> val;
        --ty;
        --y;
        --x;
    }
    Converted prob = convert(r, c, q, l, p, queries);
    Vec<i32> ans = solve(prob);
    for (i32 ele : ans) {
        cout << ele << '\n';
    }
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	16984 KB	Output is correct
2	Correct	94 ms	23844 KB	Output is correct
3	Correct	122 ms	34656 KB	Output is correct
4	Correct	91 ms	17124 KB	Output is correct
5	Correct	97 ms	23404 KB	Output is correct
6	Correct	119 ms	34428 KB	Output is correct
7	Correct	83 ms	13540 KB	Output is correct
8	Correct	96 ms	21792 KB	Output is correct
9	Correct	84 ms	15836 KB	Output is correct
10	Correct	111 ms	34568 KB	Output is correct
11	Correct	98 ms	25444 KB	Output is correct
12	Correct	135 ms	43992 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	17972 KB	Output is correct
2	Correct	109 ms	26460 KB	Output is correct
3	Correct	138 ms	38780 KB	Output is correct
4	Correct	112 ms	19816 KB	Output is correct
5	Correct	113 ms	27088 KB	Output is correct
6	Correct	138 ms	38168 KB	Output is correct
7	Correct	210 ms	13924 KB	Output is correct
8	Correct	284 ms	30336 KB	Output is correct
9	Correct	219 ms	16768 KB	Output is correct
10	Correct	336 ms	64268 KB	Output is correct
11	Correct	285 ms	40708 KB	Output is correct
12	Correct	314 ms	87360 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	196 ms	20080 KB	Output is correct
2	Correct	411 ms	20160 KB	Output is correct
3	Correct	600 ms	20360 KB	Output is correct
4	Correct	603 ms	22372 KB	Output is correct
5	Correct	437 ms	22336 KB	Output is correct
6	Correct	198 ms	21896 KB	Output is correct
7	Correct	693 ms	20208 KB	Output is correct
8	Correct	741 ms	20124 KB	Output is correct
9	Correct	699 ms	20344 KB	Output is correct
10	Correct	695 ms	20336 KB	Output is correct
11	Correct	706 ms	20232 KB	Output is correct
12	Correct	653 ms	22484 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	16984 KB	Output is correct
2	Correct	94 ms	23844 KB	Output is correct
3	Correct	122 ms	34656 KB	Output is correct
4	Correct	91 ms	17124 KB	Output is correct
5	Correct	97 ms	23404 KB	Output is correct
6	Correct	119 ms	34428 KB	Output is correct
7	Correct	83 ms	13540 KB	Output is correct
8	Correct	96 ms	21792 KB	Output is correct
9	Correct	84 ms	15836 KB	Output is correct
10	Correct	111 ms	34568 KB	Output is correct
11	Correct	98 ms	25444 KB	Output is correct
12	Correct	135 ms	43992 KB	Output is correct
13	Correct	172 ms	21904 KB	Output is correct
14	Correct	496 ms	37080 KB	Output is correct
15	Correct	688 ms	67472 KB	Output is correct
16	Correct	629 ms	24356 KB	Output is correct
17	Correct	564 ms	36112 KB	Output is correct
18	Correct	204 ms	41632 KB	Output is correct
19	Correct	331 ms	18900 KB	Output is correct
20	Correct	500 ms	32928 KB	Output is correct
21	Correct	378 ms	21088 KB	Output is correct
22	Correct	484 ms	56484 KB	Output is correct
23	Correct	488 ms	40304 KB	Output is correct
24	Correct	473 ms	71140 KB	Output is correct

Subtask #5

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	16984 KB	Output is correct
2	Correct	94 ms	23844 KB	Output is correct
3	Correct	122 ms	34656 KB	Output is correct
4	Correct	91 ms	17124 KB	Output is correct
5	Correct	97 ms	23404 KB	Output is correct
6	Correct	119 ms	34428 KB	Output is correct
7	Correct	83 ms	13540 KB	Output is correct
8	Correct	96 ms	21792 KB	Output is correct
9	Correct	84 ms	15836 KB	Output is correct
10	Correct	111 ms	34568 KB	Output is correct
11	Correct	98 ms	25444 KB	Output is correct
12	Correct	135 ms	43992 KB	Output is correct
13	Correct	101 ms	17972 KB	Output is correct
14	Correct	109 ms	26460 KB	Output is correct
15	Correct	138 ms	38780 KB	Output is correct
16	Correct	112 ms	19816 KB	Output is correct
17	Correct	113 ms	27088 KB	Output is correct
18	Correct	138 ms	38168 KB	Output is correct
19	Correct	210 ms	13924 KB	Output is correct
20	Correct	284 ms	30336 KB	Output is correct
21	Correct	219 ms	16768 KB	Output is correct
22	Correct	336 ms	64268 KB	Output is correct
23	Correct	285 ms	40708 KB	Output is correct
24	Correct	314 ms	87360 KB	Output is correct
25	Correct	196 ms	20080 KB	Output is correct
26	Correct	411 ms	20160 KB	Output is correct
27	Correct	600 ms	20360 KB	Output is correct
28	Correct	603 ms	22372 KB	Output is correct
29	Correct	437 ms	22336 KB	Output is correct
30	Correct	198 ms	21896 KB	Output is correct
31	Correct	693 ms	20208 KB	Output is correct
32	Correct	741 ms	20124 KB	Output is correct
33	Correct	699 ms	20344 KB	Output is correct
34	Correct	695 ms	20336 KB	Output is correct
35	Correct	706 ms	20232 KB	Output is correct
36	Correct	653 ms	22484 KB	Output is correct
37	Correct	172 ms	21904 KB	Output is correct
38	Correct	496 ms	37080 KB	Output is correct
39	Correct	688 ms	67472 KB	Output is correct
40	Correct	629 ms	24356 KB	Output is correct
41	Correct	564 ms	36112 KB	Output is correct
42	Correct	204 ms	41632 KB	Output is correct
43	Correct	331 ms	18900 KB	Output is correct
44	Correct	500 ms	32928 KB	Output is correct
45	Correct	378 ms	21088 KB	Output is correct
46	Correct	484 ms	56484 KB	Output is correct
47	Correct	488 ms	40304 KB	Output is correct
48	Correct	473 ms	71140 KB	Output is correct
49	Correct	196 ms	25624 KB	Output is correct
50	Correct	597 ms	44360 KB	Output is correct
51	Correct	786 ms	79900 KB	Output is correct
52	Correct	681 ms	29044 KB	Output is correct
53	Correct	627 ms	43484 KB	Output is correct
54	Correct	245 ms	48592 KB	Output is correct
55	Correct	660 ms	20768 KB	Output is correct
56	Correct	956 ms	47036 KB	Output is correct
57	Correct	676 ms	24808 KB	Output is correct
58	Correct	932 ms	110208 KB	Output is correct
59	Correct	948 ms	66168 KB	Output is correct
60	Correct	941 ms	148716 KB	Output is correct