oj.uz

Submission #229511

# Submission time Handle Problem Language Result Execution time Memory
229511 2020-05-04T21:12:15 Z Haunted_Cpp Game (IOI13_game) C++17
37 / 100
 1508 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

vector< vector<long long> > seg;

int _R, _C;

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;
}

void update_coluna (int l, int r, int node, long long delta, int coluna, int node_linha, bool is_merge) {
  if (l > coluna || r < coluna) return;
  if (l == coluna && r == coluna) {
    if (is_merge) seg[node_linha][node] = delta;
    else seg[node_linha][node] = gcd2 (seg[2 * node_linha + 1][node], seg[2 * node_linha + 2][node]);
    return;
  }
  int mid = l + (r - l) / 2;
  update_coluna (l, mid, 2 * node + 1, delta, coluna, node_linha, is_merge);
  update_coluna (mid + 1, r, 2 * node + 2, delta, coluna, node_linha, is_merge);
  if (is_merge) {
    seg[node_linha][node] = gcd2 (seg[node_linha][2 * node + 1], seg[node_linha][2 * node + 2]);
  } else {
    seg[node_linha][node] = gcd2 (seg[2 * node_linha + 1][node], seg[2 * node_linha + 2][node]);
  }
}

void update_linha (int l, int r, int node, int linha, long long delta, int coluna) {
  if (l > linha || r < linha) return;
  if (l == linha && r == linha) {
    update_coluna (0, _C - 1, 0, delta, coluna, node, true);
    return;
  }
  int mid = l + (r - l) / 2;
  update_linha (l, mid, 2 * node + 1, linha, delta, coluna);
  update_linha (mid + 1, r, 2 * node + 2, linha, delta, coluna);
  update_coluna (0, _C - 1, 0, delta, coluna, node, false);
}

long long query_coluna (int l, int r, int node, int coluna_inicio, int coluna_fim, int node_linha) {
  if (l > coluna_fim || r < coluna_inicio) return 0;
  if (l >= coluna_inicio && r <= coluna_fim) return seg[node_linha][node];
  int mid = l + (r - l) / 2;
  return gcd2 ( query_coluna (l, mid, 2 * node + 1, coluna_inicio, coluna_fim, node_linha), 
  query_coluna (mid + 1, r, 2 * node + 2, coluna_inicio, coluna_fim, node_linha) );
}

long long query_linha (int l, int r, int node, int linha_inicio, int linha_fim, int coluna_inicio, int coluna_fim) {
  if (l > linha_fim || r < linha_inicio) return 0;
  if (l >= linha_inicio && r <= linha_fim) {
    return query_coluna (0, _C - 1, 0, coluna_inicio, coluna_fim, node);
  }
  int mid = l + (r - l) / 2;
  return gcd2 ( query_linha (l, mid, 2 * node + 1, linha_inicio, linha_fim, coluna_inicio, coluna_fim), 
  query_linha (mid + 1, r, 2 * node + 2, linha_inicio, linha_fim, coluna_inicio, coluna_fim) );
}


void init(int R, int C) {
  _R = R;
  _C = C;
  seg = vector< vector<long long> > (4 * R, vector<long long> (4 * C, 0LL));
}

void update(int P, int Q, long long K) {
  update_linha (0, _R - 1, 0, P, K, Q);
}

long long calculate(int P, int Q, int U, int V) {
  return query_linha (0, _R - 1, 0, 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 1536 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 5 ms 1536 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 4 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 802 ms 134252 KB Output is correct
5 Correct 608 ms 134068 KB Output is correct
6 Correct 741 ms 131580 KB Output is correct
7 Correct 733 ms 131260 KB Output is correct
8 Correct 644 ms 131516 KB Output is correct
9 Correct 728 ms 131384 KB Output is correct
10 Correct 687 ms 131124 KB Output is correct
11 Correct 4 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 6 ms 1664 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 5 ms 1536 KB Output is correct
12 Correct 1073 ms 134008 KB Output is correct
13 Correct 1495 ms 130552 KB Output is correct
14 Runtime error 164 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 5 ms 1536 KB Output is correct
12 Correct 798 ms 134200 KB Output is correct
13 Correct 630 ms 133944 KB Output is correct
14 Correct 725 ms 131512 KB Output is correct
15 Correct 726 ms 131188 KB Output is correct
16 Correct 658 ms 131640 KB Output is correct
17 Correct 736 ms 131516 KB Output is correct
18 Correct 667 ms 131132 KB Output is correct
19 Correct 1053 ms 134008 KB Output is correct
20 Correct 1508 ms 130552 KB Output is correct
21 Runtime error 168 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 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 1664 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 5 ms 416 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 5 ms 1664 KB Output is correct
12 Correct 775 ms 134332 KB Output is correct
13 Correct 598 ms 134072 KB Output is correct
14 Correct 745 ms 131512 KB Output is correct
15 Correct 734 ms 131388 KB Output is correct
16 Correct 629 ms 131644 KB Output is correct
17 Correct 735 ms 131260 KB Output is correct
18 Correct 689 ms 131132 KB Output is correct
19 Correct 1054 ms 134068 KB Output is correct
20 Correct 1497 ms 130424 KB Output is correct
21 Runtime error 160 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -