Submission #1261180

#TimeUsernameProblemLanguageResultExecution timeMemory
1261180repmannGame (IOI13_game)C++20
0 / 100
130 ms321536 KiB
#include <bits/stdc++.h> #include "game.h" #define ll long long using namespace std; int cntR, cntC; struct ColNode { ll gcd; int LC, RC; int L, R; ColNode() { gcd = LC = RC = L = R = 0; return; } ColNode(int lc, int rc) { gcd = L = R = 0; LC = lc; RC = rc; return; } }COL[10000000]; struct RowNode { ll gcd; int LC, RC; int L, R; int col; RowNode() { gcd = LC = RC = L = R = col = 0; return; } RowNode(int lc, int rc) { gcd = L = R = col = 0; LC = lc; RC = rc; return; } }ROW[10000000]; void init(int R, int C) { ROW[++cntR] = RowNode(1, 1 << 30); return; } void Merge(ColNode *node) { node->gcd = __gcd(COL[node->L].gcd, COL[node->R].gcd); return; } void ColUpdate(int j, ll x, ColNode *node) { if(node->LC == node->RC) { node->gcd = x; return; } int S = (node->LC + node->RC) >> 1; if(j <= S) { if(!node->L) {node->L = ++cntC; COL[cntC] = ColNode(node->LC, S);} ColUpdate(j, x, &COL[node->L]); } else { if(!node->R) {node->R = ++cntC; COL[cntC] = ColNode(S + 1, node->RC);} ColUpdate(j, x, &COL[node->R]); } Merge(node); return; } ll ColPoint(int j, ColNode *node) { if(node == COL) return 0; if(node->LC == node->RC) return node->gcd; int S = (node->LC + node->RC) >> 1; if(j <= S) { if(!node->L) return 0; return ColPoint(j, &COL[node->L]); } else { if(!node->R) return 0; return ColPoint(j, &COL[node->R]); } return 0; } void Update(int i, int j, ll x, RowNode *node) { if(node->LC == node->RC) { if(!node->col) {node->col = ++cntC; COL[cntC] = ColNode(1, 1 << 30);} ColUpdate(j, x, &COL[node->col]); return; } int S = (node->LC + node->RC) >> 1; if(i <= S) { if(!node->L) {node->L = ++cntR; ROW[cntR] = RowNode(node->LC, S);} Update(i, j, x, &ROW[node->L]); } else { if(!node->R) {node->R = ++cntR; ROW[cntR] = RowNode(S + 1, node->RC);} Update(i, j, x, &ROW[node->R]); } if(!node->col) {node->col = ++cntC; COL[cntC] = ColNode(1, 1 << 30);} ll l = 0, r = 0; if(node->L) l = ColPoint(j, &COL[ROW[node->L].col]); if(node->R) r = ColPoint(j, &COL[ROW[node->R].col]); ColUpdate(j, __gcd(l, r), &COL[node->col]); return; } void update(int i, int j, ll x) { i++; j++; Update(i, j, x, &ROW[1]); return; } ll ColGet(int j, int l, ColNode *node) { if(node == COL) return 0; if((node->LC > l) || (j > node->RC)) return 0; if((j <= node->LC) && (node->RC <= l)) return node->gcd; return __gcd(ColGet(j, l, &COL[node->L]), ColGet(j, l, &COL[node->R])); } ll Get(int i, int j, int k, int l, RowNode *node) { if(node == ROW) return 0; if((node->LC > k) || (i > node->RC)) return 0; if((i <= node->LC) && (node->RC <= k)) { if(!node->col) return 0; return ColGet(j, l, &COL[node->col]); } return __gcd(Get(i, j, k, l, &ROW[node->L]), Get(i, j, k, l, &ROW[node->R])); } ll calculate(int i, int j, int k, int l) { i++; j++; k++; l++; return Get(i, j, k, l, &ROW[1]); } //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...