Submission #1094021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094021	2024-09-28T10:28:56 Z	ASIXER	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KB

game

// https://www.acmicpc.net/problem/8876
#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[100000];
struct XNode {
    int lb, rb;
    ll val = 0;
    int lc = -1, rc = -1;
} x_tree[100000];

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];
        if ((lcn.lb <= xl && xl <= lcn.rb) || (lcn.lb <= xr && xr <= lcn.rb)) ret = gcd(ret, x_query(lcn, xl, xr));
    }
    if (x_node.rc != -1) {
        XNode& rcn = x_tree[x_node.rc];
        if ((rcn.lb <= xl && xl <= rcn.rb) || (rcn.lb <= xr && xr <= rcn.rb)) 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 << "\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];
        if ((lcn.lb <= yl && yl <= lcn.rb) || (lcn.lb <= yr && yr <= lcn.rb)) ret = gcd(ret, y_query(lcn, yl, yr, xl, xr));
    }
    if (y_node.rc != -1) {
        YNode& rcn = y_tree[y_node.rc];
        if ((rcn.lb <= yl && yl <= rcn.rb) || (rcn.lb <= yr && yr <= rcn.rb)) 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 solve() {
    cin >> r >> c >> q;
    init_y_node(1, r);
    while (q--) {
        int qt;
        cin >> qt;
        if (qt == 1) {
            int y, x;
            ll k;
            cin >> y >> x >> k;
            y_update(y_tree[0], y + 1, x + 1, k);
        } else {
            int y1, x1, y2, x2;
            cin >> y1 >> x1 >> y2 >> x2;
            cout << y_query(y_tree[0], y1 + 1, y2 + 1, x1 + 1, x2 + 1) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

Compilation message

/usr/bin/ld: /tmp/ccgV3EiR.o: in function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpR2U6R.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccpR2U6R.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status