Submission #729385

#TimeUsernameProblemLanguageResultExecution timeMemory
729385kevlu8게임 (IOI13_game)C++17
100 / 100
3003 ms82228 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) int n, m, q; struct node1d { node1d(int v, int x, int y) : v(v), x(x), y(y), l(NULL), r(NULL) {} ll v; int x, y; // range node1d *l, *r; }; struct node2d { node2d() : l(NULL), r(NULL), segtree(0, 1, m) {} node2d *l, *r; node1d segtree; } *root; void update1d(node1d *root, int i, ll v) { int s = root->x, e = root->y, mid = (s + e) >> 1; if (s == e) { root->v = v; return; } node1d **child = &(i <= mid ? root->l : root->r); if (*child == NULL) { *child = new node1d(v, i, i); (*child)->v = v; } else if ((*child)->x <= i && i <= (*child)->y) { update1d(*child, i, v); } else { do { if (i <= mid) e = mid; else s = mid + 1; mid = (s + e) >> 1; } while ((i <= mid) == ((*child)->y <= mid)); node1d *node2 = new node1d(0, s, e); if ((*child)->y <= mid) node2->l = *child; else node2->r = *child; *child = node2; update1d(*child, i, v); } root->v = __gcd(root->l ? root->l->v : 0, root->r ? root->r->v : 0); } ll calculate1d(node1d *root, int l, int r) { if (root == NULL || root->x > r || root->y < l) return 0; if (l <= root->x && root->y <= r) { return root->v; } return __gcd(calculate1d(root->l, l, r), calculate1d(root->r, l, r)); } void update2d(node2d *root, int l, int r, int x, int y, ll v) { if (l == r) { update1d(&root->segtree, y, v); return; } int mid = (l + r) >> 1; if (x <= mid) { if (root->l == NULL) root->l = new node2d(); update2d(root->l, l, mid, x, y, v); } else { if (root->r == NULL) root->r = new node2d(); update2d(root->r, mid+1, r, x, y, v); } ll value = __gcd(root->l ? calculate1d(&root->l->segtree, y, y) : 0, root->r ? calculate1d(&root->r->segtree, y, y) : 0); update1d(&root->segtree, y, value); } ll calculate2d(node2d *root, int l, int r, int x, int y, int x2, int y2) { if (root == NULL || l > x2 || r < x) return 0; if (x <= l && r <= x2) return calculate1d(&root->segtree, y, y2); int mid = (l + r) >> 1; return __gcd(calculate2d(root->l, l, mid, x, y, x2, y2), calculate2d(root->r, mid+1, r, x, y, x2, y2)); } void init(int n, int m) { ::n = n; ::m = m; root = new node2d(); } void update(int x, int y, ll v) { ++x, ++y; update2d(root, 1, n, x, y, v); } ll calculate(int x, int y, int x2, int y2) { ++x, ++y, ++x2, ++y2; return calculate2d(root, 1, n, x, y, x2, y2); }
#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...