Submission #518872

#	Time	Username	Problem	Language	Result	Execution time	Memory
518872		tabr	Game (IOI13_game)	C++17	0 / 100	153 ms	256004 KiB

game

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifndef tabr
#include "game.h"
#endif

template <class F>
struct y_combinator_result {
    F f;

    template <class T>
    explicit y_combinator_result(T &&f_) : f(std::forward<T>(f_)) {}

    template <class... Args>
    decltype(auto) operator()(Args &&...args) {
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class F>
decltype(auto) y_combinator(F &&f) {
    return y_combinator_result<std::decay_t<F>>(std::forward<F>(f));
}

struct node {
    long long val = 0;
    int xlow = 0;
    int xhigh = 1 << 30;
    int ylow = 0;
    int yhigh = 1 << 30;
    node *xl = nullptr;
    node *xr = nullptr;
    node *yl = nullptr;
    node *yr = nullptr;
};

node *root;

void init(int, int) {
    root = new node;
}

long long get(node *v) {
    if (v == nullptr) {
        return 0LL;
    } else {
        return v->val;
    }
}

void update(int x, int y, long long k) {
    y_combinator([&](auto dfs, node *v) -> void {
        int xmid = (v->xlow + v->xhigh) >> 1;
        int ymid = (v->ylow + v->yhigh) >> 1;
        if (v->xlow == xmid && v->ylow == ymid) {
            v->val = k;
        }
        if (v->ylow <= y && y < xmid) {
            if (v->yl == nullptr) {
                v->yl = new node;
                v->yl->xhigh = v->xhigh;
                v->yl->xlow = v->xlow;
                v->yl->ylow = v->ylow;
                v->yl->yhigh = ymid;
            }
            dfs(v->yl);
        } else {
            if (v->yr == nullptr) {
                v->yr = new node;
                v->yr->xhigh = v->xhigh;
                v->yr->xlow = v->xlow;
                v->yr->ylow = ymid;
                v->yr->yhigh = v->yhigh;
            }
            dfs(v->yr);
        }
        if (v->xlow <= x && x < xmid) {
            if (v->xl == nullptr) {
                v->xl = new node;
                v->xl->xlow = v->xlow;
                v->xl->xhigh = xmid;
            }
            dfs(v->xl);
        } else {
            if (v->xr == nullptr) {
                v->xr = new node;
                v->xr->xlow = xmid;
                v->xr->xhigh = v->xhigh;
            }
            dfs(v->xr);
        }
        v->val = __gcd(get(v->xl), get(v->xr));
    })(root);
}

long long calculate(int x1, int y1, int x2, int y2) {
    x2++, y2++;
    return y_combinator([&](auto dfs, node *v) -> long long {
        if (v == nullptr) {
            return 0LL;
        }
        if (v->xlow <= x1 || x2 <= v->xhigh || v->ylow <= y1 || y2 <= v->yhigh) {
            return 0LL;
        }
        if (x1 <= v->xlow && v->xhigh <= x2) {
            if (y1 <= v->ylow && v->yhigh <= y2) {
                return v->val;
            }
            return __gcd(dfs(v->yl), dfs(v->yr));
        } else {
            return __gcd(dfs(v->xl), dfs(v->xr));
        }
    })(root);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w, n;
    cin >> h >> w >> n;
    init(h, w);
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int p, q, k;
            cin >> p >> q >> k;
            update(p, q, k);
        } else {
            int p, q, u, v;
            cin >> p >> q >> u >> v;
            cout << calculate(p, q, u, v) << '\n';
        }
    }
    return 0;
}
#endif

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20