oj.uz

Submission #229595

# Submission time Handle Problem Language Result Execution time Memory
229595 2020-05-05T09:20:55 Z Haunted_Cpp Game (IOI13_game) C++17
63 / 100
 1892 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 512 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 4 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 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 597 ms 12840 KB Output is correct
5 Correct 425 ms 13048 KB Output is correct
6 Correct 505 ms 9976 KB Output is correct
7 Correct 585 ms 9752 KB Output is correct
8 Correct 398 ms 6904 KB Output is correct
9 Correct 586 ms 9840 KB Output is correct
10 Correct 522 ms 9336 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 4 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 512 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 929 ms 16016 KB Output is correct
13 Correct 1446 ms 6392 KB Output is correct
14 Correct 328 ms 1016 KB Output is correct
15 Correct 1737 ms 8952 KB Output is correct
16 Correct 251 ms 18424 KB Output is correct
17 Correct 971 ms 11656 KB Output is correct
18 Correct 1628 ms 18832 KB Output is correct
19 Correct 1284 ms 18964 KB Output is correct
20 Correct 1208 ms 18408 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 5 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 4 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 594 ms 12740 KB Output is correct
13 Correct 420 ms 13200 KB Output is correct
14 Correct 515 ms 9976 KB Output is correct
15 Correct 575 ms 9700 KB Output is correct
16 Correct 384 ms 6780 KB Output is correct
17 Correct 565 ms 9848 KB Output is correct
18 Correct 517 ms 9336 KB Output is correct
19 Correct 914 ms 15836 KB Output is correct
20 Correct 1475 ms 6520 KB Output is correct
21 Correct 338 ms 1016 KB Output is correct
22 Correct 1749 ms 9160 KB Output is correct
23 Correct 237 ms 18424 KB Output is correct
24 Correct 875 ms 11640 KB Output is correct
25 Correct 1463 ms 19028 KB Output is correct
26 Correct 1262 ms 19012 KB Output is correct
27 Correct 1234 ms 18296 KB Output is correct
28 Correct 1038 ms 256000 KB Output is correct
29 Runtime error 1892 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 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 512 KB Output is correct
7 Correct 4 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 590 ms 12664 KB Output is correct
13 Correct 411 ms 13048 KB Output is correct
14 Correct 506 ms 10164 KB Output is correct
15 Correct 603 ms 9976 KB Output is correct
16 Correct 389 ms 6776 KB Output is correct
17 Correct 567 ms 9888 KB Output is correct
18 Correct 502 ms 9352 KB Output is correct
19 Correct 900 ms 15992 KB Output is correct
20 Correct 1482 ms 6264 KB Output is correct
21 Correct 330 ms 1056 KB Output is correct
22 Correct 1751 ms 8952 KB Output is correct
23 Correct 241 ms 18424 KB Output is correct
24 Correct 865 ms 11648 KB Output is correct
25 Correct 1506 ms 18756 KB Output is correct
26 Correct 1215 ms 18936 KB Output is correct
27 Correct 1167 ms 18408 KB Output is correct
28 Correct 1052 ms 256000 KB Output is correct
29 Runtime error 1860 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -