Submission #1094085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094085		ASIXER	Game (IOI13_game)	C++17	0 / 100	19 ms	43484 KiB

game

#include "game.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;

struct YNode {
    int lb, rb;
    int x_root = -1;
    int lc = -1, rc = -1;
} y_tree[1000000];
struct XNode {
    int lb, rb;
    ll val = 0;
    int lc = -1, rc = -1;
} x_tree[1000000];

int r, c, q;
int y_cnt = 0, x_cnt = 0;

int init_x_node(int lb, int rb) {
    XNode& x_node = x_tree[x_cnt];
    x_node.lb = lb, x_node.rb = rb;
    return x_cnt++;
}
int init_y_node(int lb, int rb) {
    YNode& y_node = y_tree[y_cnt];
    y_node.lb = lb, y_node.rb = rb;
    y_node.x_root = init_x_node(1, c);
    return y_cnt++;
}

ll x_query(XNode& x_node, int xl, int xr) {
    // cout << "x query " << x_node.lb << " ~ " << x_node.rb << " (qrange: " << xl << " ~ " << xr << ")\n";
    if (xr < x_node.lb || x_node.rb < xl) return 0;
    else if (xl <= x_node.lb && x_node.rb <= xr) return x_node.val;
    ll ret = 0;
    if (x_node.lc != -1) {
        XNode& lcn = x_tree[x_node.lc];
        ret = gcd(ret, x_query(lcn, xl, xr));
    }
    if (x_node.rc != -1) {
        XNode& rcn = x_tree[x_node.rc];
        ret = gcd(ret, x_query(rcn, xl, xr));
    }
    return ret;
}
ll y_query(YNode& y_node, int yl, int yr, int xl, int xr) {
    // cout << "y query " << y_node.lb << " ~ " << y_node.rb << " (qr: " << yl << " ~ " << yr << ")\n";
    if (yr < y_node.lb || y_node.rb < yl) return 0;
    else if (yl <= y_node.lb && y_node.rb <= yr) return x_query(x_tree[y_node.x_root], xl, xr);
    ll ret = 0;
    if (y_node.lc != -1) {
        YNode& lcn = y_tree[y_node.lc];
        ret = gcd(ret, y_query(lcn, yl, yr, xl, xr));
    }
    if (y_node.rc != -1) {
        YNode& rcn = y_tree[y_node.rc];
        ret = gcd(ret, y_query(rcn, yl, yr, xl, xr));
    }
    return ret;
}

void x_update(XNode& x_node, int x, ll val) {
    if (x < x_node.lb || x_node.rb < x) return;
    if (x_node.lb == x_node.rb) {
        x_node.val = val;
        return;
    }
    int mid = (x_node.lb + x_node.rb) >> 1;
    if (x <= mid) {
        if (x_node.lc == -1) {
            x_node.lc = init_x_node(x, x);
            XNode& lcn = x_tree[x_node.lc];
            x_update(lcn, x, val);
        } else {
            XNode& lcn = x_tree[x_node.lc];
            if (lcn.lb <= x && x <= lcn.rb) x_update(lcn, x, val);
            else {
                int mmid = (x_node.lb + mid) >> 1;
                int new_lc_idx = init_x_node(x_node.lb, mid);
                XNode& new_lcn = x_tree[new_lc_idx];
                if (lcn.rb <= mmid) new_lcn.lc = x_node.lc;
                else new_lcn.rc = x_node.lc;
                x_node.lc = new_lc_idx;
                x_update(new_lcn, x, val);
            }
        }
    } else {
        if (x_node.rc == -1) {
            x_node.rc = init_x_node(x, x);
            XNode& rcn = x_tree[x_node.rc];
            x_update(rcn, x, val);
        } else {
            XNode& rcn = x_tree[x_node.rc];
            if (rcn.lb <= x && x <= rcn.rb) x_update(rcn, x, val);
            else {
                int mmid = (mid + 1 + x_node.rb) >> 1;
                int new_rc_idx = init_x_node(mid + 1, x_node.rb);
                XNode& new_rcn = x_tree[new_rc_idx];
                if (rcn.rb <= mmid) new_rcn.lc = x_node.rc;
                else new_rcn.rc = x_node.rc;
                x_node.rc = new_rc_idx;
                x_update(new_rcn, x, val);
            }
        }
    }

    ll new_val = 0;
    if (x_node.lc != -1) new_val = gcd(new_val, x_tree[x_node.lc].val);
    if (x_node.rc != -1) new_val = gcd(new_val, x_tree[x_node.rc].val);
    // cout << "x upd result: " << x_node.lb << " " << x_node.rb << ": " << new_val << "\n";
    x_node.val = new_val;
}

void y_update(YNode& y_node, int y, int x, ll val) {
    // cout << "y upd " << y_node.lb << " ~ " << y_node.rb << " (p: " << y << ")\n";
    if (y < y_node.lb || y_node.rb < y) {
        return;
    }
    if (y_node.lb == y_node.rb) return x_update(x_tree[y_node.x_root], x, val);
    int mid = (y_node.lb + y_node.rb) >> 1;
    if (y <= mid) {
        if (y_node.lc == -1) {
            // update 할 범위의 노드가 없는 경우 - leaf 노드 생성
            y_node.lc = init_y_node(y, y);
            YNode& lcn = y_tree[y_node.lc];
            y_update(lcn, y, x, val);
        } else {
            // update 할 범위의 노드가 있는 경우
            YNode& lcn = y_tree[y_node.lc];
            if (lcn.lb <= y && y <= lcn.rb)  // 그리고 그 노드가 업데이트 범위를 포함하는 경우
                y_update(lcn, y, x, val);
            else {
                // 또는 그 노드가 업데이트 범위를 포함하지 않는 경우 -> lb < mid 임이 보장됨
                int mmid = (y_node.lb + mid) >> 1;
                int new_lc_idx = init_y_node(y_node.lb, mid);
                YNode& new_lcn = y_tree[new_lc_idx];
                if (lcn.rb <= mmid) new_lcn.lc = y_node.lc;
                else new_lcn.rc = y_node.lc;
                y_node.lc = new_lc_idx;
                y_update(new_lcn, y, x, val);
            }
        }
    } else {
        if (y_node.rc == -1) {
            // update 할 범위의 노드가 없는 경우 - leaf 노드 생성
            y_node.rc = init_y_node(y, y);
            YNode& rcn = y_tree[y_node.rc];
            y_update(rcn, y, x, val);
        } else {
            // update 할 범위의 노드가 있는 경우
            YNode& rcn = y_tree[y_node.rc];
            if (rcn.lb <= y && y <= rcn.rb)  // 그리고 그 노드가 업데이트 범위를 포함하는 경우
                y_update(rcn, y, x, val);
            else {
                // 또는 그 노드가 업데이트 범위를 포함하지 않는 경우 -> mid + 1 < rb 임이 보장됨
                int mmid = (mid + 1 + y_node.rb) >> 1;
                int new_rc_idx = init_y_node(mid + 1, y_node.rb);
                YNode& new_rcn = y_tree[new_rc_idx];
                if (rcn.rb <= mmid) new_rcn.lc = y_node.rc;
                else new_rcn.rc = y_node.rc;
                y_node.rc = new_rc_idx;
                y_update(new_rcn, y, x, val);
            }
        }
    }

    ll new_val = 0;
    if (y_node.lc != -1) new_val = gcd(new_val, x_query(x_tree[y_tree[y_node.lc].x_root], x, x));
    if (y_node.rc != -1) new_val = gcd(new_val, x_query(x_tree[y_tree[y_node.rc].x_root], x, x));

    x_update(x_tree[y_node.x_root], x, new_val);
}

void init(int rr, int cc) { r = rr, c = cc, init_y_node(1, r); }

void update(int y, int x, ll k) { y_update(y_tree[0], y + 1, x + 1, k); }

ll calculate(int y1, int x1, int y2, int x2) { return y_query(y_tree[0], y1 + 1, y2 + 1, x1 + 1, x2 + 1); }

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