Submission #229585

#	Time	Username	Problem	Language	Result	Execution time	Memory
229585		Haunted_Cpp	Game (IOI13_game)	C++17	63 / 100	1849 ms	256004 KiB

game

#include "game.h"
#include <iostream>
using namespace std;

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

struct Seg {
  Seg *l, *r;
  long long sum;
  Seg () {
    l = r = nullptr;
    sum = 0;
  }
};

struct Node {
  Node *l, *r;
  Seg *segmentTree;
  long long sum;
  Node () {
    l = r = nullptr;
    sum = 0;
  }
};

Node *root;

int _R, _C;

void update_coluna (Seg *&cur, int l, int r, int coluna, long long delta, Seg *esq, Seg *dir) {
  if (l > coluna || r < coluna) return;
  if (l == coluna && r == coluna) {
    if (esq == nullptr && dir == nullptr) {
      cur -> sum = delta;
    } else {
      cur -> sum = gcd2 ( (esq ? esq -> sum : 0) , (dir ? dir -> sum : 0) );
    }
    return;
  }

  int mid = l + (r - l) / 2;
  if (mid >= coluna) {
    if (!cur -> l) cur -> l = new Seg;
    update_coluna (cur -> l, l, mid, coluna, delta, (esq && esq -> l ? esq -> l : nullptr), (dir && dir -> l ? dir -> l: nullptr) );
  }
  if (mid + 1 <= coluna) {
    if (!cur -> r) cur -> r = new Seg;
    update_coluna (cur -> r, mid + 1, r, coluna, delta, (esq && esq -> r ? esq -> r : nullptr), (dir && dir -> r ? dir -> r : nullptr) );
  }

  if (esq == nullptr && dir == nullptr) {
    cur -> sum = gcd2 ( (cur -> l ? cur -> l -> sum : 0), (cur -> r ? cur -> r -> sum : 0) );
  } else {
    cur -> sum = gcd2 ( (esq ? esq -> sum : 0), (dir ? dir -> sum : 0) );
  }


}

void update_linha (Node *&cur, int l, int r, int linha, long long delta, int coluna) {
  if (l > linha || r < linha) return;
  if (l == linha && r == linha) {
    if (!cur -> segmentTree) cur -> segmentTree = new Seg;
    update_coluna (cur -> segmentTree, 0, _C - 1, coluna, delta, nullptr, nullptr);
    return;
  }
  int mid = l + (r - l) / 2;
  if (mid >= linha) {
    if (!cur -> l) cur -> l = new Node;
    update_linha (cur -> l, l, mid, linha, delta, coluna);
  }
  if (mid + 1 <= linha) {
    if (!cur -> r) cur -> r = new Node;
    update_linha (cur -> r, mid + 1, r, linha, delta, coluna);
  }
  if (!cur -> segmentTree) cur -> segmentTree = new Seg;
  update_coluna (cur -> segmentTree, 0, _C - 1, coluna, delta, (cur -> l ? cur -> l -> segmentTree: nullptr), (cur -> r ? cur -> r -> segmentTree : nullptr) );
}


void init(int R, int C) {
  root = new Node;
  _R = R;
  _C = C;
}

void update(int P, int Q, long long K) {
  update_linha (root, 0, _R - 1, P, K, Q);
}

long long query_coluna (Seg* cur, int l, int r, int coluna_inicial, int coluna_final) {
  if (!cur || l > coluna_final || r < coluna_inicial) return 0;
  if (l >= coluna_inicial && r <= coluna_final) {
    return cur -> sum;
  }
  int mid = l + (r - l) / 2;
  return gcd2 ( query_coluna (cur -> l, l, mid, coluna_inicial, coluna_final ),query_coluna (cur -> r, mid + 1, r, coluna_inicial, coluna_final ) );
}

long long query_linha (Node* cur, int l, int r, int linha_inicial, int linha_final, int coluna_inicial, int coluna_final) {
  if (!cur || l > linha_final || r < linha_inicial) return 0;
  if (l >= linha_inicial && r <= linha_final) {
    return query_coluna (cur -> segmentTree, 0, _C - 1, coluna_inicial, coluna_final);
  }
  int mid = l + (r - l) / 2;
  return gcd2 ( query_linha (cur -> l, l, mid, linha_inicial, linha_final, coluna_inicial, coluna_final ),query_linha (cur -> r, mid + 1, r, linha_inicial, linha_final, coluna_inicial, coluna_final ) );
}

long long calculate(int P, int Q, int U, int V) {
  return query_linha (root, 0, _R - 1, P, U, Q, V);
}

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