oj.uz

Submission #229585

# Submission time Handle Problem Language Result Execution time Memory
229585 2020-05-05T09:02:43 Z Haunted_Cpp Game (IOI13_game) C++17
63 / 100
 1849 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;

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

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 384 KB Output is correct
2 Correct 5 ms 384 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 384 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 384 KB Output is correct
9 Correct 6 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 5 ms 512 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 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 574 ms 13044 KB Output is correct
5 Correct 429 ms 13332 KB Output is correct
6 Correct 485 ms 10104 KB Output is correct
7 Correct 568 ms 9976 KB Output is correct
8 Correct 403 ms 7060 KB Output is correct
9 Correct 541 ms 10104 KB Output is correct
10 Correct 491 ms 9724 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 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 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 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 887 ms 16252 KB Output is correct
13 Correct 1486 ms 6552 KB Output is correct
14 Correct 336 ms 1260 KB Output is correct
15 Correct 1795 ms 9156 KB Output is correct
16 Correct 238 ms 18680 KB Output is correct
17 Correct 836 ms 11840 KB Output is correct
18 Correct 1425 ms 18936 KB Output is correct
19 Correct 1287 ms 19448 KB Output is correct
20 Correct 1190 ms 18572 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 512 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 630 ms 13048 KB Output is correct
13 Correct 447 ms 13308 KB Output is correct
14 Correct 533 ms 10232 KB Output is correct
15 Correct 644 ms 10104 KB Output is correct
16 Correct 431 ms 6904 KB Output is correct
17 Correct 561 ms 9976 KB Output is correct
18 Correct 530 ms 9568 KB Output is correct
19 Correct 888 ms 16300 KB Output is correct
20 Correct 1530 ms 6568 KB Output is correct
21 Correct 339 ms 1272 KB Output is correct
22 Correct 1849 ms 9152 KB Output is correct
23 Correct 235 ms 18680 KB Output is correct
24 Correct 836 ms 12024 KB Output is correct
25 Correct 1400 ms 18948 KB Output is correct
26 Correct 1222 ms 19208 KB Output is correct
27 Correct 1189 ms 18424 KB Output is correct
28 Correct 1054 ms 256000 KB Output is correct
29 Runtime error 1833 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 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 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 384 KB Output is correct
9 Correct 5 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 586 ms 13384 KB Output is correct
13 Correct 430 ms 13600 KB Output is correct
14 Correct 499 ms 10360 KB Output is correct
15 Correct 560 ms 10064 KB Output is correct
16 Correct 380 ms 7160 KB Output is correct
17 Correct 553 ms 10232 KB Output is correct
18 Correct 507 ms 9704 KB Output is correct
19 Correct 880 ms 16376 KB Output is correct
20 Correct 1494 ms 6644 KB Output is correct
21 Correct 344 ms 1400 KB Output is correct
22 Correct 1762 ms 9276 KB Output is correct
23 Correct 233 ms 18808 KB Output is correct
24 Correct 876 ms 12100 KB Output is correct
25 Correct 1427 ms 19068 KB Output is correct
26 Correct 1217 ms 19448 KB Output is correct
27 Correct 1226 ms 18552 KB Output is correct
28 Correct 1074 ms 256000 KB Output is correct
29 Runtime error 1792 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -