Submission #689597

#	Time	Username	Problem	Language	Result	Execution time	Memory
689597		Mamedov	Game (IOI13_game)	C++17	0 / 100	2 ms	596 KiB

game

#pragma GCC optimize ("O3")
#include "game.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXR = 1e9;
const int MAXC = 1e9;

struct tree1D {
  tree1D *left, *right;
  ll GCD;
  tree1D(): left(nullptr), right(nullptr), GCD(0) {}
  void update1D(tree1D *tr, int l, int r, int pos, ll val) {
    if (l == r) {
      tr->GCD = val;
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        if (tr->left == nullptr) tr->left = new tree1D();
        update1D(tr->left, l, mid, pos, val);
      } else {
        if (tr->right == nullptr) tr->right = new tree1D();
        update1D(tr->right, mid + 1, r, pos, val);
      }
      if (tr->left == nullptr) tr->GCD = tr->right->GCD;
      else if (tr->right == nullptr) tr->GCD = tr->left->GCD;
      else tr->GCD = __gcd(tr->left->GCD, tr->right->GCD);
    }
  }
  ll query1D(tree1D *tr, int l, int r, int ql, int qr) {
    if (ql > r || l > qr) return 0;
    else if (ql <= l && r <= qr) return tr->GCD;
    else {
      int mid = (l + r) >> 1;
      ll q1 = 0, q2 = 0;
      if (tr->left != nullptr) q1 = query1D(tr->left, l, mid, ql, qr);
      if (tr->right != nullptr) q2 = query1D(tr->right, mid + 1, r, ql, qr);
      return __gcd(q1, q2);
    }
  }
};

struct tree2D {
  tree2D *left, *right;
  tree1D *tree_1D;
  tree2D(): left(nullptr), right(nullptr), tree_1D(new tree1D()) {}
  void update2D(tree2D *tr, int l, int r, int pos_r, int pos_c, ll val) {
    tr->tree_1D->update1D(tr->tree_1D, 1, MAXC, pos_c, val);
    if (l < r) {
      int mid = (l + r) >> 1;
      if (pos_r <= mid) {
        if (tr->left == nullptr) tr->left = new tree2D();
        update2D(tr->left, l, mid, pos_r, pos_c, val);
      } else {
        if (tr->right == nullptr) tr->right = new tree2D();
        update2D(tr->right, mid + 1, r, pos_r, pos_c, val);
      }
    }
  }
  ll query2D(tree2D *tr, int l, int r, int row_l, int row_r, int col_l, int col_r) {
    if (row_l > r || l > row_r) return 0;
    else if (row_l <= l && r <= row_r) return tr->tree_1D->query1D(tr->tree_1D, 1, MAXC, col_l, col_r);
    else {
      int mid = (l + r) >> 1;
      ll q1 = 0, q2 = 0;
      if (tr->left != nullptr) q1 = query2D(tr->left, l, mid, row_l, row_r, col_l, col_r);
      if (tr->right != nullptr) q2 = query2D(tr->right, mid + 1, r, row_l, row_r, col_l, col_r);
      return __gcd(q1, q2);
    }
  }
};

/// usage
/// tree2D *tr = new tree2D()
/// tr->update2D(tr, 1, MAXR, row, col, val)
/// tr->query2D(tr, 1, MAXR, row_l, row_r, col_l, col_r)

tree2D *tr;
void init(int R, int C) {
  tr = new tree2D();
}

void update(int P, int Q, ll K) {
  ++P;
  ++Q;
  tr->update2D(tr, 1, MAXR, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
  ++P;
  ++Q;
  ++U;
  ++V;
  return tr->query2D(tr, 1, MAXR, P, U, Q, V);
}

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