Submission #672306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672306	2022-12-15T12:18:51 Z	Forested	I want to be the very best too! (NOI17_pokemonmaster)	C++17	51 / 100	693 ms	87904 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);
    auto add = [&](i32 v, i32 k) -> void {
        for (auto [l, r] : hld.path(prob.rt, v, false)) {
            ++r;
            segs[k].update(l, segs[k].prod(l, l + 1) + 1);
            segs[k].update(r, segs[k].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[k].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 k) -> void {
        for (auto [l, r] : hld.path(prob.rt, v, false)) {
            ++r;
            segs[k].update(l, segs[k].prod(l, l + 1) - 1);
            segs[k].update(r, segs[k].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[k].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<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	79 ms	17376 KB	Output is correct
2	Correct	92 ms	24328 KB	Output is correct
3	Correct	112 ms	35064 KB	Output is correct
4	Correct	85 ms	17472 KB	Output is correct
5	Correct	95 ms	23756 KB	Output is correct
6	Correct	112 ms	34780 KB	Output is correct
7	Correct	80 ms	13868 KB	Output is correct
8	Correct	91 ms	22108 KB	Output is correct
9	Correct	83 ms	16208 KB	Output is correct
10	Correct	119 ms	34916 KB	Output is correct
11	Correct	99 ms	25948 KB	Output is correct
12	Correct	128 ms	44412 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	18536 KB	Output is correct
2	Correct	112 ms	27076 KB	Output is correct
3	Correct	137 ms	39344 KB	Output is correct
4	Correct	96 ms	20456 KB	Output is correct
5	Correct	110 ms	27660 KB	Output is correct
6	Correct	130 ms	38708 KB	Output is correct
7	Correct	211 ms	14608 KB	Output is correct
8	Correct	250 ms	30820 KB	Output is correct
9	Correct	210 ms	17256 KB	Output is correct
10	Correct	294 ms	64996 KB	Output is correct
11	Correct	264 ms	41200 KB	Output is correct
12	Correct	315 ms	87904 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	22376 KB	Output is correct
2	Correct	410 ms	22064 KB	Output is correct
3	Correct	577 ms	21880 KB	Output is correct
4	Correct	578 ms	23992 KB	Output is correct
5	Correct	426 ms	24144 KB	Output is correct
6	Correct	190 ms	23928 KB	Output is correct
7	Correct	680 ms	22224 KB	Output is correct
8	Correct	693 ms	21964 KB	Output is correct
9	Correct	657 ms	22084 KB	Output is correct
10	Correct	658 ms	22096 KB	Output is correct
11	Incorrect	625 ms	22064 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	17376 KB	Output is correct
2	Correct	92 ms	24328 KB	Output is correct
3	Correct	112 ms	35064 KB	Output is correct
4	Correct	85 ms	17472 KB	Output is correct
5	Correct	95 ms	23756 KB	Output is correct
6	Correct	112 ms	34780 KB	Output is correct
7	Correct	80 ms	13868 KB	Output is correct
8	Correct	91 ms	22108 KB	Output is correct
9	Correct	83 ms	16208 KB	Output is correct
10	Correct	119 ms	34916 KB	Output is correct
11	Correct	99 ms	25948 KB	Output is correct
12	Correct	128 ms	44412 KB	Output is correct
13	Correct	187 ms	23796 KB	Output is correct
14	Correct	480 ms	39120 KB	Output is correct
15	Correct	634 ms	69448 KB	Output is correct
16	Correct	588 ms	26160 KB	Output is correct
17	Correct	482 ms	37944 KB	Output is correct
18	Correct	200 ms	43580 KB	Output is correct
19	Correct	348 ms	20740 KB	Output is correct
20	Correct	493 ms	34900 KB	Output is correct
21	Correct	357 ms	22948 KB	Output is correct
22	Correct	429 ms	58392 KB	Output is correct
23	Correct	475 ms	42176 KB	Output is correct
24	Correct	457 ms	73144 KB	Output is correct

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	17376 KB	Output is correct
2	Correct	92 ms	24328 KB	Output is correct
3	Correct	112 ms	35064 KB	Output is correct
4	Correct	85 ms	17472 KB	Output is correct
5	Correct	95 ms	23756 KB	Output is correct
6	Correct	112 ms	34780 KB	Output is correct
7	Correct	80 ms	13868 KB	Output is correct
8	Correct	91 ms	22108 KB	Output is correct
9	Correct	83 ms	16208 KB	Output is correct
10	Correct	119 ms	34916 KB	Output is correct
11	Correct	99 ms	25948 KB	Output is correct
12	Correct	128 ms	44412 KB	Output is correct
13	Correct	94 ms	18536 KB	Output is correct
14	Correct	112 ms	27076 KB	Output is correct
15	Correct	137 ms	39344 KB	Output is correct
16	Correct	96 ms	20456 KB	Output is correct
17	Correct	110 ms	27660 KB	Output is correct
18	Correct	130 ms	38708 KB	Output is correct
19	Correct	211 ms	14608 KB	Output is correct
20	Correct	250 ms	30820 KB	Output is correct
21	Correct	210 ms	17256 KB	Output is correct
22	Correct	294 ms	64996 KB	Output is correct
23	Correct	264 ms	41200 KB	Output is correct
24	Correct	315 ms	87904 KB	Output is correct
25	Correct	187 ms	22376 KB	Output is correct
26	Correct	410 ms	22064 KB	Output is correct
27	Correct	577 ms	21880 KB	Output is correct
28	Correct	578 ms	23992 KB	Output is correct
29	Correct	426 ms	24144 KB	Output is correct
30	Correct	190 ms	23928 KB	Output is correct
31	Correct	680 ms	22224 KB	Output is correct
32	Correct	693 ms	21964 KB	Output is correct
33	Correct	657 ms	22084 KB	Output is correct
34	Correct	658 ms	22096 KB	Output is correct
35	Incorrect	625 ms	22064 KB	Output isn't correct
36	Halted	0 ms	0 KB	-