제출 #569684

#제출 시각아이디문제언어결과실행 시간메모리
569684Noam527게임 (IOI13_game)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> typedef long long ll; typedef long double ldb; const int md = (int)1e9 + 7; const ll inf = 2e18; const int OO = 1; using namespace std; #include "game.h" /* the struct 'element' must have: * neutral element (as default constructor) * operator *, to combine with a right operand and return the result also note the "using T = ll". this is the range of indicies we allow. can change to int for efficiency. */ template<typename element> struct segtree { using T = ll; struct node { element val; int l, r; node(element v = element()) { l = -1, r = -1, val = v; } }; T L, R; vector<node> t; segtree() {} segtree(T LL, T RR) { L = LL, R = RR; t.push_back(node()); } int add_node() { t.push_back(node()); return (int)t.size() - 1; } int go_left(int v) { if (t[v].l == -1) { // this prevents a bug that might occur when t.push_back provokes reallocation int x = add_node(); t[v].l = x; } return t[v].l; } int go_right(int v) { if (t[v].r == -1) { // this prevents a bug that might occur when t.push_back provokes reallocation int x = add_node(); t[v].r = x; } return t[v].r; } void fix(int v) { // assumes v has at least 1 child if (t[v].l == -1) t[v].val = t[t[v].r].val; else if (t[v].r == -1) t[v].val = t[t[v].l].val; else t[v].val = t[t[v].l].val * t[t[v].r].val; } void update(T pos, element val) { update(pos, val, 0, L, R); } void update(T pos, element val, int node, T nl, T nr) { if (nl == nr) { t[node].val = val; return; } T mid = (nl + nr) / 2; if (pos <= mid) update(pos, val, go_left(node), nl, mid); else update(pos, val, go_right(node), mid + 1, nr); fix(node); } element get(T i) { int node = 0; T l = L, r = R; while (l < r) { T mid = (l + r) / 2; if (i <= mid) { if (t[node].l == -1) return element(); node = t[node].l; l = mid + 1; } else { if (t[node].r == -1) return element(); node = t[node].r; r = mid; } } return t[node].val; } element query(T l, T r) { if (l > r) return element(); return query(l, r, 0, L, R); } element query(T l, T r, int node, T nl, T nr) { if (r < nl || nr < l) return element(); if (l <= nl && nr <= r) return t[node].val; T mid = (nl + nr) / 2; if (r <= mid || t[node].r == -1) { if (t[node].l == -1) return element(); return query(l, r, go_left(node), nl, mid); } if (mid < l || t[node].l == -1) return query(l, r, go_right(node), mid + 1, nr); return query(l, r, t[node].l, nl, mid) * query(l, r, t[node].r, mid + 1, nr); } }; /* the struct 'element' must have: * neutral element (as default constructor) * operator *, to combine with a right operand and return the result also note the "using T = ll". this is the range of indicies we allow. can change to int for efficiency. */ template<typename element> struct segtree2D { using T = ll; struct node { segtree<element> val; int l, r; node() {} node(T L, T R) { l = -1, r = -1; val = segtree<element>(L, R); } }; T L0, R0, L1, R1; vector<node> t; segtree2D() {} segtree2D(T l0, T r0, T l1, T r1) { L0 = l0; R0 = r0; L1 = l1; R1 = r1; t.push_back(node(L1, R1)); } int add_node() { t.push_back(node(L1, R1)); return (int)t.size() - 1; } int go_left(int v) { if (t[v].l == -1) { // this prevents a bug that might occur when t.push_back provokes reallocation int x = add_node(); t[v].l = x; } return t[v].l; } int go_right(int v) { if (t[v].r == -1) { // this prevents a bug that might occur when t.push_back provokes reallocation int x = add_node(); t[v].r = x; } return t[v].r; } void fix(int node, T pos1) { // assumes node has at least 1 child element val; if (t[node].l == -1) val = t[t[node].r].val.get(pos1); else if (t[node].r == -1) val = t[t[node].l].val.get(pos1); else val = t[t[node].l].val.get(pos1) * t[t[node].r].val.get(pos1); t[node].val.update(pos1, val); } void update(T pos0, T pos1, element val) { update(pos0, pos1, val, 0, L0, R0); } void update(T pos0, T pos1, element val, int node, T nl, T nr) { if (nl == nr) { t[node].val.update(pos1, val); return; } T mid = (nl + nr) / 2; if (pos0 <= mid) update(pos0, pos1, val, go_left(node), nl, mid); else update(pos0, pos1, val, go_right(node), mid + 1, nr); fix(node, pos1); } element query(T l0, T r0, T l1, T r1) { if (l0 > r0 || l1 > r1) return element(); return query(l0, r0, l1, r1, 0, L0, R0); } element query(T l0, T r0, T l1, T r1, int node, T nl, T nr) { if (r0 < nl || nr < l0) return element(); if (l0 <= nl && nr <= r0) return t[node].val.query(l1, r1); T mid = (nl + nr) / 2; if (r0 <= mid || t[node].r == -1) { if (t[node].l == -1) return element(); return query(l0, r0, l1, r1, go_left(node), nl, mid); } if (mid < l0 || t[node].l == -1) return query(l0, r0, l1, r1, go_right(node), mid + 1, nr); return query(l0, r0, l1, r1, t[node].l, nl, mid) * query(l0, r0, l1, r1, t[node].r, mid + 1, nr); } }; ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); } struct ele { ll x; ele(ll xx = 0) : x(xx) {} ele operator * (const ele &a) const { return ele(gcd(x, a.x)); } }; segtree2D<ele> T; void init(int R, int C) { T = segtree2D<ele>(0, R - 1, 0, C - 1); } void update(int p, int q, ll k) { T.update(p, q, k); } ll calculate(int p, int q, int u, int v) { return T.query(p, u, q, v).x; }
#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...