Submission #1261056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261056		repmann	Game (IOI13_game)	C++20	63 / 100	2137 ms	321536 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
struct ColNode
{
  ll gcd;
  int LC, RC;
  ColNode *L, *R;
  ColNode()
  {
    gcd = LC = RC = 0;
    L = R = nullptr;
    return;
  }
  ColNode(int lc, int rc)
  {
    gcd = 0;
    LC = lc;
    RC = rc;
    L = R = nullptr;
    return;
  }
  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;
  int LC, RC;
  RowNode *L, *R;
  ColNode *col;
  RowNode()
  {
    gcd = LC = RC = 0;
    L = R = nullptr;
    col = nullptr;
    return;
  }
  RowNode(int lc, int rc)
  {
    gcd = 0;
    LC = lc;
    RC = rc;
    L = R = nullptr;
    col = nullptr;
    return;
  }
}*root;
void init(int R, int C)
{
  root = new RowNode(1, 1 << 30);
  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 = new ColNode(node->LC, S);
    ColUpdate(j, x, node->L);
  }
  else
  {
    if(!node->R) node->R = new ColNode(S + 1, node->RC);
    ColUpdate(j, x, node->R);
  }
  node->Merge();
  return;
}
ll ColPoint(int j, ColNode *node)
{
  if(!node) 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, node->L);
  }
  else
  {
    if(!node->R) return 0;
    return ColPoint(j, node->R);
  }
  return 0;
}
void Update(int i, int j, ll x, RowNode *node)
{
  if(node->LC == node->RC)
  {
    if(!node->col) node->col = new ColNode(1, 1 << 30);
    ColUpdate(j, x, node->col);
    return;
  }
  int S = (node->LC + node->RC) >> 1;
  if(i <= S)
  {
    if(!node->L) node->L = new RowNode(node->LC, S);
    Update(i, j, x, node->L);
  }
  else
  {
    if(!node->R) node->R = new RowNode(S + 1, node->RC);
    Update(i, j, x, node->R);
  }
  if(!node->col) node->col = new ColNode(1, 1 << 30);
  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)
{
  if(!node) 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, node->L), ColGet(j, l, node->R));
}
ll Get(int i, int j, int k, int l, RowNode *node)
{
  if(!node) 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, node->col);
  }
  return __gcd(Get(i, j, k, l, node->L), Get(i, j, k, l, node->R));
}
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;
//}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20