제출 #1261245

#제출 시각아이디문제언어결과실행 시간메모리
1261245repmannGame (IOI13_game)C++20
63 / 100
1151 ms282512 KiB
#include <bits/stdc++.h> #include "game.h" #define ll long long using namespace std; int WR, WC; struct ColNode { ll gcd; ColNode *L, *R; void Merge() { ll l = 0, r = 0; if(L) l = this->L->gcd; if(R) r = this->R->gcd; this->gcd = __gcd(l, r); return; } }; struct RowNode { ll gcd; RowNode *L, *R; ColNode *col; }*root; void init(int R, int C) { WR = 1; while(WR < R) WR <<= 1; WC = 1; while(WC < C) WC <<= 1; root = new RowNode(); return; } void ColUpdate(int j, ll x, ColNode *node, int LC = 1, int RC = WC) { if(LC == RC) { node->gcd = x; return; } int S = (LC + RC) >> 1; if(j <= S) { if(!node->L) node->L = new ColNode(); ColUpdate(j, x, node->L, LC, S); } else { if(!node->R) node->R = new ColNode(); ColUpdate(j, x, node->R, S + 1, RC); } node->Merge(); return; } ll ColPoint(int j, ColNode *node, int LC = 1, int RC = WC) { if(!node) return 0; if(LC == RC) return node->gcd; int S = (LC + RC) >> 1; if(j <= S) { if(!node->L) return 0; return ColPoint(j, node->L, LC, S); } else { if(!node->R) return 0; return ColPoint(j, node->R, S + 1, RC); } return 0; } void Update(int i, int j, ll x, RowNode *node, int LC = 1, int RC = WR) { if(LC == RC) { if(!node->col) node->col = new ColNode(); ColUpdate(j, x, node->col); return; } int S = (LC + RC) >> 1; if(i <= S) { if(!node->L) node->L = new RowNode(); Update(i, j, x, node->L, LC, S); } else { if(!node->R) node->R = new RowNode(); Update(i, j, x, node->R, S + 1, RC); } if(!node->col) node->col = new ColNode(); ll l = 0, r = 0; if(node->L) l = ColPoint(j, node->L->col); if(node->R) r = ColPoint(j, node->R->col); ColUpdate(j, __gcd(l, r), node->col); return; } void update(int i, int j, ll x) { i++; j++; Update(i, j, x, root); return; } ll ColGet(int j, int l, ColNode *node, int LC = 1, int RC = WC) { if(!node) return 0; if((LC > l) || (j > RC)) return 0; if((j <= LC) && (RC <= l)) return node->gcd; int S = (LC + RC) >> 1; return __gcd(ColGet(j, l, node->L, LC, S), ColGet(j, l, node->R, S + 1, RC)); } ll Get(int i, int j, int k, int l, RowNode *node, int LC = 1, int RC = WR) { if(!node) return 0; if((LC > k) || (i > RC)) return 0; if((i <= LC) && (RC <= k)) { if(!node->col) return 0; return ColGet(j, l, node->col); } int S = (LC + RC) >> 1; return __gcd(Get(i, j, k, l, node->L, LC, S), Get(i, j, k, l, node->R, S + 1, RC)); } ll calculate(int i, int j, int k, int l) { i++; j++; k++; l++; return Get(i, j, k, l, root); } //int main() //{ // int r, c; // cin >> r >> c; // init(r, c); // int t, i, j, l; // ll k; // while(true) // { // cin >> t >> i >> j >> k; // if(t == 1) update(i, j, k); // else // { // cin >> l; // cout << calculate(i, j, k, l) << '\n'; // } // } // return 0; //}
#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...