제출 #1190973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190973		tyellow	게임 (IOI13_game)	C++20	63 / 100	1098 ms	278808 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()


int n, m;

struct SegNode1D {
    ll val = 0;
    SegNode1D *lp = nullptr, *rp = nullptr;
};

struct SegmentTree1D {
    SegNode1D *node = new SegNode1D;

    void modify(int l, int r, SegNode1D *&p, int q, ll val) {
        if (p == nullptr)
            p = new SegNode1D;
        if (l == r) {
            p->val = val;
            return;
        }
        int mid = l + r >> 1;
        if (q <= mid)
            modify(l, mid, p->lp, q, val);
        else
            modify(mid + 1, r, p->rp, q, val);
        p->val = gcd(p->lp ? p->lp->val : 0, p->rp ? p->rp->val : 0);
    }
    void modify(int q, ll val) { modify(1, m, node, q, val); }

    ll query(int l, int r, SegNode1D *&p, int ql, int qr) {
        if (!p || ql > r || qr < l) return 0;
        if (ql <= l && r <= qr)
            return p->val;
        int mid = l + r >> 1;
        return gcd(p->lp ? query(l, mid, p->lp, ql, qr) : 0, p->rp ? query(mid + 1, r, p->rp, ql, qr) : 0);
    }
    ll query(int ql, int qr) { return query(1, m, node, ql, qr); }
};

struct SegNode2D {
    SegmentTree1D val;
    SegNode2D *lp = nullptr, *rp = nullptr;
};

struct SegmentTree2D {
    SegNode2D *node = new SegNode2D;

    void modify(int l, int r, SegNode2D *&p, int x, int y, ll val) {
        if (p == nullptr)
            p = new SegNode2D;
        if (l == r) {
            p->val.modify(y, val);
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid)
            modify(l, mid, p->lp, x, y, val);
        else 
            modify(mid + 1, r, p->rp, x, y, val);
        p->val.modify(y, gcd(p->lp ? p->lp->val.query(y, y) : 0, p->rp ? p->rp->val.query(y, y) : 0));
    }
    void modify(int x, int y, ll val) { modify(1, n, node, x, y, val); }

    ll query(int l, int r, SegNode2D *&p, int U, int D, int L, int R) {
        if (!p || U > r || D < l) return 0;
        if (U <= l && r <= D)
            return p->val.query(L, R);
        int mid = l + r >> 1;
        return gcd(p->lp ? query(l, mid, p->lp, U, D, L, R) : 0, p->rp ? query(mid + 1, r, p->rp, U, D, L, R) : 0);
    }
    ll query(int U, int D, int L, int R) { return query(1, n, node, U, L, D, R); }

} tree;

void init(int R, int C) {
    n = R, m = C;
}

void update(int P, int Q, ll K) {
    tree.modify(++P, ++Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return tree.query(++P, ++Q, ++U, ++V);
}

// int main() {
//     cin.tie(0)->sync_with_stdio(0);
//     int Q;
//     cin >> n >> m >> Q;
//     while (Q--) {
//         int type;
//         cin >> type;
//         if (type == 1) {
//             int p, q; ll k;
//             cin >> p >> q >> k;
//             tree.modify(++p, ++q, k);
//         } else {
//             int p, q, u, v;
//             cin >> p >> q >> u >> v;
//             cout << tree.query(++p, ++q, ++u, ++v) << '\n';
//         }
//     }
//     return 0;
// }

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