제출 #1246776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246776		Amadoo	게임 (IOI13_game)	C++20	0 / 100	1 ms	328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const long long MAX = 1e18;

using T = long long;
inline T merge(const T &a, const T &b) { return gcd(a, b); }
const T default_val = 0;

struct NodeY {
    NodeY *l = nullptr, *r = nullptr;
    T val = default_val;
};

struct NodeX {
    NodeX *l = nullptr, *r = nullptr;
    NodeY *st = nullptr;
};

struct ImplicitSegTree2D {
    int x_min, x_max, y_min, y_max;
    NodeX *root = nullptr;
    ImplicitSegTree2D() {}
    ImplicitSegTree2D(int _x_min, int _x_max, int _y_min, int _y_max) : x_min(_x_min), x_max(_x_max), y_min(_y_min), y_max(_y_max) {}
    void updateY(NodeY *&node, int ly, int ry, int y, const T &v) {
        if(!node) node = new NodeY();
        if(ly == ry) {
            node->val = merge(node->val, v);
            return;
        }
        int mid = ly + (ry - ly) / 2;
        if(y <= mid) updateY(node->l, ly, mid, y, v);
        else updateY(node->r, mid + 1, ry, y, v);
        T lv = node->l ? node->l->val : default_val;
        T rv = node->r ? node->r->val : default_val;
        node->val = merge(lv, rv);
    }
    void updateX(NodeX *&node, int lx, int rx, int x, int y, const T &v) {
        if(!node) node = new NodeX();
        updateY(node->st, y_min, y_max, y, v);
        if(lx == rx) return;
        int mid = lx + (rx - lx) / 2;
        if(x <= mid) updateX(node->l, lx, mid, x, y, v);
        else updateX(node->r, mid + 1, rx, x, y, v);
    }
    void update(int x, int y, const T &v) {
        if(x < x_min || x > x_max || y < y_min || y > y_max) return;
        updateX(root, x_min, x_max, x, y, v);
    }
    T queryY(NodeY *node, int ly, int ry, int ql, int qr) const {
        if(!node || qr < ly || ry < ql) return default_val;
        if(ql <= ly && ry <= qr) return node->val;
        int mid = ly + (ry - ly) / 2;
        return merge(queryY(node->l, ly, mid, ql, qr), queryY(node->r, mid + 1, ry, ql, qr));
    }
    T queryX(NodeX *node, int lx, int rx, int qx1, int qx2, int qy1, int qy2) const {
        if(!node || qx2 < lx || rx < qx1) return default_val;
        if(qx1 <= lx && rx <= qx2) return queryY(node->st, y_min, y_max, qy1, qy2);
        int mid = lx + (rx - lx) / 2;
        return merge(queryX(node->l, lx, mid, qx1, qx2, qy1, qy2), queryX(node->r, mid + 1, rx, qx1, qx2, qy1, qy2));
    }
    T query(int x1, int y1, int x2, int y2) const {
        if(x2 < x_min || x_max < x1 || y2 < y_min || y_max < y1) return default_val;
        x1 = max(x1, x_min); x2 = min(x2, x_max);
        y1 = max(y1, y_min); y2 = min(y2, y_max);
        return queryX(root, x_min, x_max, x1, x2, y1, y2);
    }
};

ImplicitSegTree2D st;

void init(int R, int C) {
    st = ImplicitSegTree2D(0, R, 0, C);
}

void update(int P, int Q, long long K) {
    st.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st.query(P, Q, U, V);
}

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