제출 #375732

#제출 시각아이디문제언어결과실행 시간메모리
375732vot808게임 (IOI13_game)C++17
80 / 100
4193 ms256004 KiB
#include "bits/stdc++.h" #include "game.h" #ifdef mlocal #include "grader.c" #endif using namespace std; #define for_(i, s, e) for (int i = s; i < (int) e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; #define endl '\n' int MXR, MXC; const int MXL = 660000; struct SegmentTree { public: vector<ii> c; vector<ll> tree; int pt = 1; void update(int &i, ll &val, int l, int r, int p, int &xc0, int &xc1, int &corresp0, int &corresp1, SegmentTree xtree[]) { if (l == r) { if (!xc0 and !xc1) tree[p] = val; else { tree[p] = __gcd((xc0 and corresp0) ? xtree[xc0].tree[corresp0] : 0, (xc1 and corresp1) ? xtree[xc1].tree[corresp1] : 0); } return; } int mid = (l+r)/2, s = i > mid; if (!c[p][s]) { tree.resize(pt+1); c.resize(pt+1); c[p][s] = pt++; } if (xc0 and (corresp0 or p == 0)) corresp0 = xtree[xc0].c[corresp0][s]; if (xc1 and (corresp1 or p == 0)) corresp1 = xtree[xc1].c[corresp1][s]; update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s], xc0, xc1, corresp0, corresp1, xtree); tree[p] = __gcd(c[p][0] ? tree[c[p][0]] : 0, c[p][1] ? tree[c[p][1]] : 0); } ll query(int i, int j, int l, int r, int p) { if (l > j or r < i) return 0; if (l >= i and r <= j) return tree[p]; int mid = (l+r)/2; return __gcd(c[p][0] ? query(i, j, l, mid, c[p][0]) : 0, c[p][1] ? query(i, j, mid+1, r, c[p][1]) : 0); } SegmentTree() { c.resize(1); tree.resize(1); } }; struct SegmentTree2D { public: int c[MXL][2] = {0}; SegmentTree tree[MXL]; int pt = 1; void update(int &i, int &j, ll &val, int l, int r, int p) { if (l != r) { int mid = (l+r)/2, s = i > mid; if (!c[p][s]) c[p][s] = pt++; update(i, j, val, s ? mid+1 : l, s ? r : mid, c[p][s]); } int ta = 0, tb = 0; tree[p].update(j, val, 0, MXC, 0, c[p][0], c[p][1], ta, tb, tree); } ll query(int &xi, int &xj, int &yi, int &yj, int l, int r, int p) { if (l > xj or r < xi) return 0; if (l >= xi and r <= xj) return tree[p].query(yi, yj, 0, MXC, 0); int mid = (l+r)/2; return __gcd(c[p][0] ? query(xi, xj, yi, yj, l, mid, c[p][0]) : 0, c[p][1] ? query(xi, xj, yi, yj, mid+1, r, c[p][1]) : 0); } // SegmentTree2D() { // c.resize(1); tree.resize(1); // } }; SegmentTree2D tree; void init(int R, int C) { // cout << "yellow" << endl; // Wait, do I even need to do something here? :) MXR = R, MXC = C; } void update(int P, int Q, ll K) { tree.update(P, Q, K, 0, MXR, 0); } ll calculate(int P, int Q, int U, int V) { return tree.query(P, U, Q, V, 0, MXR, 0); } // int main() { // cout << "tale" << endl; // }
#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...