oj.uz

Submission #98261

# Submission time Handle Problem Language Result Execution time Memory
98261 2019-02-21T17:59:44 Z MiricaMatei Game (IOI13_game) C++14
63 / 100
 3618 ms 257024 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int N, M;

long long gcd2(long long X, long long Y) {
  long long tmp;
  while (Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

struct Node1D {
  Node1D* left;
  Node1D* right;
  long long gcd;
};

Node1D* empty1 = new Node1D {NULL, NULL, 0};

struct Node2D {
  Node1D* root;
  Node2D* left;
  Node2D* right;
};

Node2D* empty2 = new Node2D {empty1, NULL, NULL};
Node2D* Root;

long long query2(Node1D* root, int l, int r, int q, int v);

Node1D* update2(Node1D* root, int l, int r, int q, long long val) {
  if (root == empty1)
    root = new Node1D {empty1, empty1, val};
  if (l == r) {
    root->gcd = val;
    return root;
  }
  int mid = (l + r) / 2;
  if (q <= mid)
    root->left = update2(root->left, l, mid, q, val);
  else
    root->right = update2(root->right, mid + 1, r, q, val);
  root->gcd = gcd2(root->left->gcd, root->right->gcd);
  return root;
}

Node2D* update1(Node2D* root, int l, int r, int p, int q, long long val) {
  if (root == empty2)
    root = new Node2D {empty1, empty2, empty2};
  if (l == r) {
    root->root = update2(root->root, 1, M, q, val);
    return root;
  }
  int mid = (l + r) / 2;
  if (p <= mid)
    root->left = update1(root->left, l, mid, p, q, val);
  else
    root->right = update1(root->right, mid + 1, r, p, q, val);
  val = 0;
  if (root->left->root != empty1)
    val = query2(root->left->root, 1, M, q, q);
  if (root->right->root != empty1)
    val = gcd2(val, query2(root->right->root, 1, M, q, q));
  root->root = update2(root->root, 1, M, q, val);
  return root;
}


long long query2(Node1D* root, int l, int r, int q, int v) {
  if (root == empty1)
    return 0;
  if (v < l || r < q)
    return 0;
  if (q <= l && r <= v)
    return root->gcd;
  int mid = (l + r) / 2;
  long long val = 0;
  if (q <= mid)
    val = query2(root->left, l, mid, q, v);
  if (mid < v)
    val = gcd2(val, query2(root->right, mid + 1, r, q, v));
  return val;
}

long long query1(Node2D* root, int l, int r, int p, int q, int u, int v) {
  if (root == empty2)
    return 0;
  if (u < l || r < p)
    return 0;
  if (p <= l && r <= u)
    return query2(root->root, 1, M, q, v);
  int mid = (l + r) / 2;
  long long val = 0;
  if (p <= mid)
    val = query1(root->left, l, mid, p, q, u, v);
  if (mid < u)
    val = gcd2(val, query1(root->right, mid + 1, r, p, q, u, v));
  return val;
}

void init(int R, int C) {
  Root = empty2;
  N = R;
  M = C;
}

void update(int P, int Q, long long K) {
  Root = update1(Root, 1, N, P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query1(Root, 1, N, P + 1, Q + 1, U + 1, V + 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 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 877 ms 17136 KB Output is correct
5 Correct 637 ms 16888 KB Output is correct
6 Correct 737 ms 14488 KB Output is correct
7 Correct 834 ms 14192 KB Output is correct
8 Correct 529 ms 10932 KB Output is correct
9 Correct 966 ms 14340 KB Output is correct
10 Correct 786 ms 14000 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1545 ms 20020 KB Output is correct
13 Correct 2640 ms 10160 KB Output is correct
14 Correct 467 ms 5488 KB Output is correct
15 Correct 3618 ms 13208 KB Output is correct
16 Correct 380 ms 22524 KB Output is correct
17 Correct 1730 ms 16132 KB Output is correct
18 Correct 3145 ms 23372 KB Output is correct
19 Correct 2812 ms 23288 KB Output is correct
20 Correct 2465 ms 22728 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 918 ms 17144 KB Output is correct
13 Correct 645 ms 16928 KB Output is correct
14 Correct 844 ms 14716 KB Output is correct
15 Correct 967 ms 14236 KB Output is correct
16 Correct 515 ms 11000 KB Output is correct
17 Correct 1095 ms 14308 KB Output is correct
18 Correct 909 ms 13896 KB Output is correct
19 Correct 1574 ms 20012 KB Output is correct
20 Correct 2673 ms 10212 KB Output is correct
21 Correct 407 ms 5428 KB Output is correct
22 Correct 3340 ms 13156 KB Output is correct
23 Correct 373 ms 22400 KB Output is correct
24 Correct 1821 ms 16004 KB Output is correct
25 Correct 3145 ms 23244 KB Output is correct
26 Correct 2577 ms 23384 KB Output is correct
27 Correct 2633 ms 22728 KB Output is correct
28 Runtime error 1720 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 540 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 963 ms 17064 KB Output is correct
13 Correct 649 ms 16908 KB Output is correct
14 Correct 856 ms 14584 KB Output is correct
15 Correct 996 ms 14264 KB Output is correct
16 Correct 588 ms 11032 KB Output is correct
17 Correct 933 ms 14340 KB Output is correct
18 Correct 927 ms 13960 KB Output is correct
19 Correct 1517 ms 19888 KB Output is correct
20 Correct 2947 ms 10228 KB Output is correct
21 Correct 369 ms 5756 KB Output is correct
22 Correct 3330 ms 13264 KB Output is correct
23 Correct 336 ms 22396 KB Output is correct
24 Correct 1618 ms 16360 KB Output is correct
25 Correct 3010 ms 23216 KB Output is correct
26 Correct 2632 ms 23324 KB Output is correct
27 Correct 2528 ms 22612 KB Output is correct
28 Runtime error 1710 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -