| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094113 | ASIXER | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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); }