제출 #645599

#제출 시각아이디문제언어결과실행 시간메모리
645599abeker게임 (IOI13_game)C++17
63 / 100
2147 ms256000 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; typedef long long ll; const int offset = 1 << 30; struct ColumnNode { ll num; ColumnNode *l, *r; ColumnNode() : num(0), l(nullptr), r(nullptr) {} }; struct RowNode { ColumnNode* root; RowNode *l, *r; RowNode() : root(new ColumnNode()), l(nullptr), r(nullptr) {} }; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } RowNode* row_root; void init(int R, int C) { row_root = new RowNode(); } ColumnNode* get_left(ColumnNode* x) { return x ? x -> l : nullptr; } ColumnNode* get_right(ColumnNode* x) { return x ? x -> r : nullptr; } ll get_num(ColumnNode* x) { return x ? x -> num : 0; } void update_col(ColumnNode *x, int lo, int hi, ColumnNode* lft, ColumnNode* rig, int col, ll val) { if (col < lo || col >= hi) return; if (hi - lo == 1) { x -> num = lft || rig ? gcd(get_num(lft), get_num(rig)) : val; return; } int mid = (lo + hi) / 2; if (!(x -> l)) x -> l = new ColumnNode(); if (!(x -> r)) x -> r = new ColumnNode(); update_col(x -> l, lo, mid, get_left(lft), get_left(rig), col, val); update_col(x -> r, mid, hi, get_right(lft), get_right(rig), col, val); x -> num = gcd(get_num(x -> l), get_num(x -> r)); } ColumnNode* get_root(RowNode* x) { return x ? x -> root : nullptr; } void update_row(RowNode* x, int lo, int hi, int row, int col, ll val) { if (row < lo || row >= hi) return; if (hi - lo > 1) { int mid = (lo + hi) / 2; if (!(x -> l)) x -> l = new RowNode(); if (!(x -> r)) x -> r = new RowNode(); update_row(x -> l, lo, mid, row, col, val); update_row(x -> r, mid, hi, row, col, val); } update_col(x -> root, 0, offset, get_root(x -> l), get_root(x -> r), col, val); } void update(int p, int q, ll k) { update_row(row_root, 0, offset, p, q, k); } ll query_col(ColumnNode* x, int lo, int hi, int from, int to) { if (!x || lo >= to || hi <= from) return 0; if (lo >= from && hi <= to) return x -> num; int mid = (lo + hi) / 2; return gcd(query_col(x -> l, lo, mid, from, to), query_col(x -> r, mid, hi, from, to)); } ll query_row(RowNode* x, int lo, int hi, int from, int to, int col1, int col2) { if (!x || lo >= to || hi <= from) return 0; if (lo >= from && hi <= to) return query_col(x -> root, 0, offset, col1, col2); int mid = (lo + hi) / 2; return gcd(query_row(x -> l, lo, mid, from, to, col1, col2), query_row(x -> r, mid, hi, from, to, col1, col2)); } ll calculate(int p, int q, int u, int v) { return query_row(row_root, 0, offset, p, u + 1, q, v + 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...