oj.uz

Submission #229589

# Submission time Handle Problem Language Result Execution time Memory
229589 2020-05-05T09:08:02 Z Haunted_Cpp Game (IOI13_game) C++17
63 / 100
 1854 ms 256004 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) {
  linha_inicial = P;
  linha_final = U;
  coluna_inicial = Q;
  coluna_final = 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 575 ms 12796 KB Output is correct
5 Correct 400 ms 13176 KB Output is correct
6 Correct 510 ms 10264 KB Output is correct
7 Correct 577 ms 9720 KB Output is correct
8 Correct 381 ms 7032 KB Output is correct
9 Correct 553 ms 10180 KB Output is correct
10 Correct 511 ms 9504 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 851 ms 16048 KB Output is correct
13 Correct 1426 ms 6392 KB Output is correct
14 Correct 325 ms 1204 KB Output is correct
15 Correct 1707 ms 9044 KB Output is correct
16 Correct 242 ms 18684 KB Output is correct
17 Correct 866 ms 11732 KB Output is correct
18 Correct 1460 ms 18936 KB Output is correct
19 Correct 1270 ms 18936 KB Output is correct
20 Correct 1259 ms 18508 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 561 ms 12792 KB Output is correct
13 Correct 390 ms 13176 KB Output is correct
14 Correct 502 ms 10108 KB Output is correct
15 Correct 567 ms 9848 KB Output is correct
16 Correct 386 ms 6776 KB Output is correct
17 Correct 551 ms 10104 KB Output is correct
18 Correct 497 ms 9592 KB Output is correct
19 Correct 870 ms 16248 KB Output is correct
20 Correct 1434 ms 6692 KB Output is correct
21 Correct 330 ms 1144 KB Output is correct
22 Correct 1677 ms 9048 KB Output is correct
23 Correct 242 ms 18560 KB Output is correct
24 Correct 866 ms 11768 KB Output is correct
25 Correct 1458 ms 18952 KB Output is correct
26 Correct 1210 ms 19256 KB Output is correct
27 Correct 1139 ms 18552 KB Output is correct
28 Correct 1026 ms 256000 KB Output is correct
29 Runtime error 1836 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 565 ms 12764 KB Output is correct
13 Correct 392 ms 13176 KB Output is correct
14 Correct 512 ms 10128 KB Output is correct
15 Correct 563 ms 9852 KB Output is correct
16 Correct 379 ms 6904 KB Output is correct
17 Correct 546 ms 10004 KB Output is correct
18 Correct 498 ms 9464 KB Output is correct
19 Correct 882 ms 16060 KB Output is correct
20 Correct 1401 ms 6648 KB Output is correct
21 Correct 334 ms 1376 KB Output is correct
22 Correct 1666 ms 9024 KB Output is correct
23 Correct 233 ms 18552 KB Output is correct
24 Correct 857 ms 12024 KB Output is correct
25 Correct 1520 ms 18936 KB Output is correct
26 Correct 1281 ms 19120 KB Output is correct
27 Correct 1204 ms 18456 KB Output is correct
28 Correct 1081 ms 256000 KB Output is correct
29 Runtime error 1854 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -