oj.uz

답안 #229588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229588 2020-05-05T09:06:50 Z Haunted_Cpp 게임 (IOI13_game) C++17
0 / 100
 6 ms 512 KB 
#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;

int linha, coluna;
long long delta;

void update_coluna (Seg *&cur, int l, int r, 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, (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, (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) {
  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, 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);
  }
  if (mid + 1 <= linha) {
    if (!cur -> r) cur -> r = new Node;
    update_linha (cur -> r, mid + 1, r);
  }
  if (!cur -> segmentTree) cur -> segmentTree = new Seg;
  update_coluna (cur -> segmentTree, 0, _C - 1, (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) {
  linha = P;
  coluna = Q;
  delta = K;
  update_linha (root, 0, _R - 1);
}

int linha_inicial, linha_final;
int coluna_inicial, coluna_final;

long long query_coluna (Seg* cur, int l, int r) {
  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),query_coluna (cur -> r, mid + 1, r) );
}

long long query_linha (Node* cur, int l, int r) {
  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);
  }
  int mid = l + (r - l) / 2;
  return gcd2 ( query_linha (cur -> l, l, mid),query_linha (cur -> r, mid + 1, r) );
}

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

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 6 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 256 KB Output is correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 6 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -