Submission #98261

#	Time	Username	Problem	Language	Result	Execution time	Memory
98261		MiricaMatei	Game (IOI13_game)	C++14	63 / 100	3618 ms	257024 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int N, M;

long long gcd2(long long X, long long Y) {
  long long tmp;
  while (Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

struct Node1D {
  Node1D* left;
  Node1D* right;
  long long gcd;
};

Node1D* empty1 = new Node1D {NULL, NULL, 0};

struct Node2D {
  Node1D* root;
  Node2D* left;
  Node2D* right;
};

Node2D* empty2 = new Node2D {empty1, NULL, NULL};
Node2D* Root;

long long query2(Node1D* root, int l, int r, int q, int v);

Node1D* update2(Node1D* root, int l, int r, int q, long long val) {
  if (root == empty1)
    root = new Node1D {empty1, empty1, val};
  if (l == r) {
    root->gcd = val;
    return root;
  }
  int mid = (l + r) / 2;
  if (q <= mid)
    root->left = update2(root->left, l, mid, q, val);
  else
    root->right = update2(root->right, mid + 1, r, q, val);
  root->gcd = gcd2(root->left->gcd, root->right->gcd);
  return root;
}

Node2D* update1(Node2D* root, int l, int r, int p, int q, long long val) {
  if (root == empty2)
    root = new Node2D {empty1, empty2, empty2};
  if (l == r) {
    root->root = update2(root->root, 1, M, q, val);
    return root;
  }
  int mid = (l + r) / 2;
  if (p <= mid)
    root->left = update1(root->left, l, mid, p, q, val);
  else
    root->right = update1(root->right, mid + 1, r, p, q, val);
  val = 0;
  if (root->left->root != empty1)
    val = query2(root->left->root, 1, M, q, q);
  if (root->right->root != empty1)
    val = gcd2(val, query2(root->right->root, 1, M, q, q));
  root->root = update2(root->root, 1, M, q, val);
  return root;
}


long long query2(Node1D* root, int l, int r, int q, int v) {
  if (root == empty1)
    return 0;
  if (v < l || r < q)
    return 0;
  if (q <= l && r <= v)
    return root->gcd;
  int mid = (l + r) / 2;
  long long val = 0;
  if (q <= mid)
    val = query2(root->left, l, mid, q, v);
  if (mid < v)
    val = gcd2(val, query2(root->right, mid + 1, r, q, v));
  return val;
}

long long query1(Node2D* root, int l, int r, int p, int q, int u, int v) {
  if (root == empty2)
    return 0;
  if (u < l || r < p)
    return 0;
  if (p <= l && r <= u)
    return query2(root->root, 1, M, q, v);
  int mid = (l + r) / 2;
  long long val = 0;
  if (p <= mid)
    val = query1(root->left, l, mid, p, q, u, v);
  if (mid < u)
    val = gcd2(val, query1(root->right, mid + 1, r, p, q, u, v));
  return val;
}

void init(int R, int C) {
  Root = empty2;
  N = R;
  M = C;
}

void update(int P, int Q, long long K) {
  Root = update1(Root, 1, N, P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query1(Root, 1, N, P + 1, Q + 1, U + 1, V + 1);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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