Submission #379563

#	Time	Username	Problem	Language	Result	Execution time	Memory
379563		WLZ	Game (IOI13_game)	C++14	100 / 100	5103 ms	101100 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int r, c;

long long gcd(long long a, long long b) {
  while (b > 0) {
    swap(a, b);
    b %= a;
  }
  return a;
}

struct node {
  int l, r, idx;
  long long val;
  node *left, *right;

  node(int _l, int _r) : l(_l), r(_r), idx(-1), val(-1), left(nullptr), right(nullptr) {}
};

void update(node *cur, int idx, long long val);

void propagate(node *cur, int idx, long long val) {
  if (idx <= (cur->l + cur->r) / 2) {
    if (cur->left == nullptr) cur->left = new node(cur->l, (cur->l + cur->r) / 2);
    update(cur->left, idx, val);
  } else {
    if (cur->right == nullptr) cur->right = new node((cur->l + cur->r) / 2 + 1, cur->r);
    update(cur->right, idx, val);
  }
}

void update(node *cur, int idx, long long val) {
  if (cur->l == cur->r) {
    cur->val = val;
    return;
  }
  if (cur->idx == idx) cur->val = val;
  else if (cur->idx != -1) {
    propagate(cur, cur->idx, cur->val);
    cur->idx = -1;
  } else if (cur->val == -1) {
    cur->idx = idx, cur->val = val;
    return;
  } 
  propagate(cur, idx, val);
  cur->val = gcd(cur->left == nullptr ? 0 : cur->left->val, cur->right == nullptr ? 0 : cur->right->val);
}

long long query(node *cur, int l, int r) {
  if (l <= cur->l && cur->r <= r) return cur->val;
  if (l > cur->r || r < cur->l) return 0;
  if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r) ? cur->val : 0;
  long long ans = 0;
  if (cur->left != nullptr) ans = gcd(ans, query(cur->left, l, r));
  if (cur->right != nullptr) ans = gcd(ans, query(cur->right, l, r));
  return ans;
}

struct node2D {
  int l, r;
  node *root;
  node2D *left, *right;

  node2D(int _l, int _r) : l(_l), r(_r), root(nullptr), left(nullptr), right(nullptr) {}
} *root;

void update2D(node2D *cur, int x, int y, long long val) {
  if (cur->root == nullptr) cur->root = new node(0, c - 1);
  if (cur->l == cur->r) {
    update(cur->root, y, val);
    return;
  }
  if (x <= (cur->l + cur->r) / 2) {
    if (cur->left == nullptr) cur->left = new node2D(cur->l, (cur->l + cur->r) / 2);
    update2D(cur->left, x, y, val);
  } else {
    if (cur->right == nullptr) cur->right = new node2D((cur->l + cur->r) / 2 + 1, cur->r);
    update2D(cur->right, x, y, val);
  }
  update(cur->root, y, gcd(cur->left == nullptr ? 0 : query(cur->left->root, y, y), cur->right == nullptr ? 0 : query(cur->right->root, y, y)));
}

long long query2D(node2D *cur, int x1, int y1, int x2, int y2) {
  if (cur->l > x2 || cur->r < x1) return 0;
  if (x1 <= cur->l && cur->r <= x2) return cur->root == nullptr ? 0 : query(cur->root, y1, y2);
  long long ans = 0;
  if (cur->left != nullptr) ans = gcd(ans, query2D(cur->left, x1, y1, x2, y2));
  if (cur->right != nullptr) ans = gcd(ans, query2D(cur->right, x1, y1, x2, y2));
  return ans;
}

void init(int R, int C) {
  r = R, c = C;
  root = new node2D(0, r - 1);
}

void update(int P, int Q, long long K) {
  update2D(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query2D(root, P, Q, U, V);
}

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