제출 #384002

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

game

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

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr int N   = 2e3 + 10;

ll gcd2(ll x, ll y) {
    ll tmp;
    while (x != y && y != 0) {
        tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}

struct Tree {
    ll data;
    pii A, B;
    Tree *ul, *ur, *dl, *dr;

    Tree(const pii & _A, const pii & _B) : data(0), A(_A), B(_B) {}

    void push(int x, int y, ll val) {
        if (x < A.X || y < A.Y || x >= B.X || y >= B.Y)
            return;
        data = gcd2(data, val);
        if (A.X + 1 == B.X) {
            assert(A.Y + 1 == B.Y);
            return;
        }
        if (ul == nullptr) {
            pii mid = {(A.X + B.X) >> 1, (A.Y + B.Y) >> 1};
            ul = new Tree({A.X, A.Y}, {mid.X, mid.Y});
            ur = new Tree({A.X, mid.Y}, {mid.X, B.Y});
            dl = new Tree({mid.X, A.Y}, {B.X, mid.Y});
            dr = new Tree({mid.X, mid.Y}, {B.X, B.Y});
        }            
        ul->push(x, y, val);
        ur->push(x, y, val);
        dl->push(x, y, val);
        dr->push(x, y, val);
    }

    ll query(const pii & C, const pii & D) {
        if (data == 0)
            return 0; // this implies ul != nullptr
        if (D.X <= A.X || D.Y <= A.Y || B.X <= C.X || B.Y <= C.Y)
            return 0;
        if (C.X <= A.X && C.Y <= A.Y && B.X <= D.X && B.Y <= D.Y)
            return data;
        ll r1 = gcd2(ul->query(C, D), ur->query(C, D)),
           r2 = gcd2(dl->query(C, D), dr->query(C, D));
        return gcd2(r1, r2);
    }
} *root;

void init(int R, int C) {
    int n = 1;
    while (n < R || n < C) {
        n <<= 1;
    }
    root = new Tree({0, 0}, {n, n});
}

void update(int P, int Q, ll K) {
    root->push(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return root->query({P, Q}, {U + 1, V + 1});
}

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