제출 #706218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706218		sharaelong	게임 (IOI13_game)	C++17	63 / 100	1576 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

struct Node1 {
    int n, ln, rn; // left node, right node
    Node1() : n(-1), ln(-1), rn(-1) {}
};

struct Node2 {
    int ln, rn;
    ll val;
    Node2() : ln(-1), rn(-1), val(0) {}
};

int R, C;
vector<Node1> node1;
vector<Node2> node2;

int new_node1() {
    node1.push_back(Node1());
    return node1.size()-1;
}

int new_node2() {
    node2.push_back(Node2());
    return node2.size()-1;
}

void update2(int n, int nl, int nr, int y, ll v) {
    if (nl == nr) {
        node2[n].val = v;
        return;
    }

    int mid = (nl + nr) / 2;
    if (y <= mid) {
        if (node2[n].ln == -1) node2[n].ln = new_node2();
        update2(node2[n].ln, nl, mid, y, v);
    } else {
        if (node2[n].rn == -1) node2[n].rn = new_node2();
        update2(node2[n].rn, mid+1, nr, y, v);
    }

    ll upd_gcd = 0;
    if (node2[n].ln != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].ln].val);
    if (node2[n].rn != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].rn].val);
    node2[n].val = upd_gcd;
}

ll query2(int n, int nl, int nr, int l, int r) {
    if (r < nl || nr < l) return 0;
    if (l <= nl && nr <= r) return node2[n].val;

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node2[n].ln != -1) ret = gcd2(ret, query2(node2[n].ln, nl, mid, l, r));
    if (node2[n].rn != -1) ret = gcd2(ret, query2(node2[n].rn, mid+1, nr, l, r));
    return ret;
}

void update1(int n, int nl, int nr, int x, int y, ll v) {
    if (node1[n].n == -1) node1[n].n = new_node2();
    if (nl == nr) {
        update2(node1[n].n, 0, C-1, y, v);
        return;
    }

    int mid = (nl + nr) / 2;
    if (x <= mid) {
        if (node1[n].ln == -1) node1[n].ln = new_node1();
        update1(node1[n].ln, nl, mid, x, y, v);
    } else {
        if (node1[n].rn == -1) node1[n].rn = new_node1();
        update1(node1[n].rn, mid+1, nr, x, y, v);
    }

    ll upd_gcd = 0;
    if (node1[n].ln != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].ln].n, 0, C-1, y, y));
    if (node1[n].rn != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].rn].n, 0, C-1, y, y));
    update2(node1[n].n, 0, C-1, y, upd_gcd);
}

ll query1(int n, int nl, int nr, int x1, int y1, int x2, int y2) {
    if (nr < x1 || x2 < nl) return 0;
    if (x1 <= nl && nr <= x2) return (node1[n].n != -1 ? query2(node1[n].n, 0, C-1, y1, y2) : 0);

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node1[n].ln != -1) ret = gcd2(ret, query1(node1[n].ln, nl, mid, x1, y1, x2, y2));
    if (node1[n].rn != -1) ret = gcd2(ret, query1(node1[n].rn, mid+1, nr, x1, y1, x2, y2));
    return ret;
}


int root;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    root = new_node1();
}

void update(int P, int Q, ll K) {
    update1(root, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R-1, P, Q, U, V);
}

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