oj.uz

Submission #229592

# Submission time Handle Problem Language Result Execution time Memory
229592 2020-05-05T09:10:58 Z Haunted_Cpp Game (IOI13_game) C++17
63 / 100
 1874 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 4 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 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 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 596 ms 12972 KB Output is correct
5 Correct 410 ms 13308 KB Output is correct
6 Correct 539 ms 10180 KB Output is correct
7 Correct 609 ms 9952 KB Output is correct
8 Correct 396 ms 6904 KB Output is correct
9 Correct 586 ms 10104 KB Output is correct
10 Correct 550 ms 9592 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
26.0 / 26.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 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 4 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 934 ms 16120 KB Output is correct
13 Correct 1486 ms 6776 KB Output is correct
14 Correct 333 ms 1260 KB Output is correct
15 Correct 1764 ms 9328 KB Output is correct
16 Correct 241 ms 18552 KB Output is correct
17 Correct 860 ms 11896 KB Output is correct
18 Correct 1507 ms 19320 KB Output is correct
19 Correct 1281 ms 19256 KB Output is correct
20 Correct 1181 ms 18524 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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 4 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 384 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 595 ms 13048 KB Output is correct
13 Correct 429 ms 13176 KB Output is correct
14 Correct 492 ms 10104 KB Output is correct
15 Correct 612 ms 9900 KB Output is correct
16 Correct 397 ms 7076 KB Output is correct
17 Correct 556 ms 9976 KB Output is correct
18 Correct 517 ms 9592 KB Output is correct
19 Correct 896 ms 16248 KB Output is correct
20 Correct 1477 ms 6524 KB Output is correct
21 Correct 324 ms 1272 KB Output is correct
22 Correct 1765 ms 9144 KB Output is correct
23 Correct 252 ms 18680 KB Output is correct
24 Correct 870 ms 11896 KB Output is correct
25 Correct 1514 ms 18860 KB Output is correct
26 Correct 1258 ms 19236 KB Output is correct
27 Correct 1151 ms 18552 KB Output is correct
28 Correct 1053 ms 256000 KB Output is correct
29 Runtime error 1856 ms 256000 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 4 ms 256 KB Output is correct
5 Correct 4 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 595 ms 12668 KB Output is correct
13 Correct 428 ms 13048 KB Output is correct
14 Correct 502 ms 9976 KB Output is correct
15 Correct 575 ms 9720 KB Output is correct
16 Correct 393 ms 6648 KB Output is correct
17 Correct 569 ms 9852 KB Output is correct
18 Correct 512 ms 9268 KB Output is correct
19 Correct 904 ms 16120 KB Output is correct
20 Correct 1465 ms 6264 KB Output is correct
21 Correct 328 ms 1020 KB Output is correct
22 Correct 1741 ms 8812 KB Output is correct
23 Correct 248 ms 18428 KB Output is correct
24 Correct 912 ms 11772 KB Output is correct
25 Correct 1460 ms 18936 KB Output is correct
26 Correct 1244 ms 18936 KB Output is correct
27 Correct 1222 ms 18424 KB Output is correct
28 Correct 1052 ms 256000 KB Output is correct
29 Runtime error 1874 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -