Submission #1094113

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

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[5e6];
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) ret = gcd(ret, x_query(x_tree[x_node.lc], xl, xr));
    if (x_node.rc != -1) ret = gcd(ret, x_query(x_tree[x_node.rc], 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) ret = gcd(ret, y_query(y_tree[y_node.lc], yl, yr, xl, xr));
    if (y_node.rc != -1) ret = gcd(ret, y_query(y_tree[y_node.rc], 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) y_node.lc = init_y_node(y_node.lb, mid);
        y_update(y_tree[y_node.lc], y, x, val);
    } else {
        if (y_node.rc == -1) y_node.rc = init_y_node(mid + 1, y_node.rb);
        y_update(y_tree[y_node.rc], 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); }

Compilation message

game.cpp:16:10: error: conversion from 'double' to 'long unsigned int' in a converted constant expression
   16 | } y_tree[5e6];
      |          ^~~
game.cpp:16:10: error: could not convert '5.0e+6' from 'double' to 'long unsigned int'
game.cpp:16:10: error: size of array 'y_tree' has non-integral type 'double'