제출 #98205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98205		MiricaMatei	게임 (IOI13_game)	C++14	63 / 100	3608 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;

int p, q, u, v;
long long val;
bool ok;

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

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


long long query2(Node1D* root, int l, int r) {
  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);
  if (mid < v)
    val = gcd2(val, query2(root->right, mid + 1, r));
  return val;
}

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

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

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

long long calculate(int P, int Q, int U, int V) {
  p = P + 1;
  q = Q + 1;
  u = U + 1;
  v = V + 1;
  return query1(Root, 1, N);
}

컴파일 시 표준 에러 (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