| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1094085 |
2024-09-28T11:54:26 Z |
ASIXER |
Game (IOI13_game) |
C++17 |
|
19 ms |
43484 KB |
#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); }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
43356 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
43380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
43356 KB |
Output is correct |
| 2 |
Correct |
16 ms |
43356 KB |
Output is correct |
| 3 |
Incorrect |
18 ms |
43352 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
43484 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
43356 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
43412 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
43276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
43484 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
43356 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
