oj.uz

Submission #229539

# Submission time Handle Problem Language Result Execution time Memory
229539 2020-05-04T23:55:03 Z Haunted_Cpp Game (IOI13_game) C++17
63 / 100
 1804 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, bool is_merge, Seg *esq, Seg *dir) {
  if (l > coluna || r < coluna) return;
  if (l == coluna && r == coluna) {
    if (is_merge == false) {
      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, is_merge, (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, is_merge, (esq && esq -> r ? esq -> r : nullptr), (dir && dir -> r ? dir -> r : nullptr) );
  }
  
  if (is_merge == false) {
    
    cur -> sum = gcd2 ( (cur -> l ? cur -> l -> sum : 0), (cur -> r ? cur -> r -> sum : 0) );
  //  cout << l << ' ' << r << ' ' << cur -> sum << '\n';
   // cout << cur << '\n';
  } 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;
   // CALL UPDATE_COLUNA
  // cout << "ENTROU: " << cur << '\n';
    update_coluna (cur -> segmentTree, 0, _C - 1, coluna, delta, false, 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, true, (cur -> l ? cur -> l -> segmentTree: nullptr), (cur -> r ? cur -> r -> segmentTree : nullptr) );
  // MERGE
}


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) {
    //cout << cur << '\n';
    //cout << "A: " << coluna_inicial << ' ' << coluna_final << ' ' << cur -> sum << '\n';
    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) {
  // cout << "Q: " << cur << '\n';
    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 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 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 4 ms 256 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 564 ms 17120 KB Output is correct
5 Correct 441 ms 17016 KB Output is correct
6 Correct 525 ms 14584 KB Output is correct
7 Correct 575 ms 14280 KB Output is correct
8 Correct 387 ms 10872 KB Output is correct
9 Correct 547 ms 14456 KB Output is correct
10 Correct 497 ms 14100 KB Output is correct
11 Correct 4 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 4 ms 384 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 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 870 ms 20192 KB Output is correct
13 Correct 1495 ms 10416 KB Output is correct
14 Correct 332 ms 5628 KB Output is correct
15 Correct 1761 ms 13464 KB Output is correct
16 Correct 241 ms 22648 KB Output is correct
17 Correct 811 ms 16504 KB Output is correct
18 Correct 1388 ms 24084 KB Output is correct
19 Correct 1170 ms 24184 KB Output is correct
20 Correct 1119 ms 23788 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 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 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 570 ms 17144 KB Output is correct
13 Correct 422 ms 17016 KB Output is correct
14 Correct 497 ms 14584 KB Output is correct
15 Correct 563 ms 14328 KB Output is correct
16 Correct 381 ms 11000 KB Output is correct
17 Correct 537 ms 14588 KB Output is correct
18 Correct 486 ms 13948 KB Output is correct
19 Correct 861 ms 20348 KB Output is correct
20 Correct 1484 ms 10160 KB Output is correct
21 Correct 344 ms 5752 KB Output is correct
22 Correct 1747 ms 13560 KB Output is correct
23 Correct 232 ms 22520 KB Output is correct
24 Correct 819 ms 16540 KB Output is correct
25 Correct 1372 ms 24092 KB Output is correct
26 Correct 1158 ms 24312 KB Output is correct
27 Correct 1099 ms 23476 KB Output is correct
28 Correct 1020 ms 256000 KB Output is correct
29 Runtime error 1722 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 512 KB Output is correct
3 Correct 5 ms 512 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 384 KB Output is correct
8 Correct 4 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 582 ms 17196 KB Output is correct
13 Correct 417 ms 16888 KB Output is correct
14 Correct 495 ms 14584 KB Output is correct
15 Correct 553 ms 14328 KB Output is correct
16 Correct 382 ms 11016 KB Output is correct
17 Correct 532 ms 14432 KB Output is correct
18 Correct 484 ms 14092 KB Output is correct
19 Correct 886 ms 19928 KB Output is correct
20 Correct 1497 ms 10264 KB Output is correct
21 Correct 333 ms 5624 KB Output is correct
22 Correct 1804 ms 13520 KB Output is correct
23 Correct 245 ms 22776 KB Output is correct
24 Correct 798 ms 16504 KB Output is correct
25 Correct 1350 ms 24064 KB Output is correct
26 Correct 1156 ms 24312 KB Output is correct
27 Correct 1100 ms 23700 KB Output is correct
28 Correct 1008 ms 256000 KB Output is correct
29 Runtime error 1719 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -