oj.uz

Submission #98205

# Submission time Handle Problem Language Result Execution time Memory
98205 2019-02-21T13:55:26 Z MiricaMatei Game (IOI13_game) C++14
63 / 100
 3608 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;

int p, q, u, v;
long long val;
bool ok;

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

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


long long query2(Node1D* root, int l, int r) {
  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);
  if (mid < v)
    val = gcd2(val, query2(root->right, mid + 1, r));
  return val;
}

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

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

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

long long calculate(int P, int Q, int U, int V) {
  p = P + 1;
  q = Q + 1;
  u = U + 1;
  v = V + 1;
  return query1(Root, 1, N);
}

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 2 ms 256 KB Output is correct
2 Correct 4 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 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 412 KB Output is correct
8 Correct 3 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 3 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 973 ms 12868 KB Output is correct
5 Correct 673 ms 13052 KB Output is correct
6 Correct 919 ms 10236 KB Output is correct
7 Correct 1066 ms 9976 KB Output is correct
8 Correct 588 ms 6888 KB Output is correct
9 Correct 1018 ms 9976 KB Output is correct
10 Correct 923 ms 9532 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 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 1594 ms 16332 KB Output is correct
13 Correct 2827 ms 6520 KB Output is correct
14 Correct 363 ms 1136 KB Output is correct
15 Correct 3429 ms 8920 KB Output is correct
16 Correct 361 ms 18504 KB Output is correct
17 Correct 1905 ms 11712 KB Output is correct
18 Correct 3330 ms 18812 KB Output is correct
19 Correct 2786 ms 18940 KB Output is correct
20 Correct 2916 ms 18364 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 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 128 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 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 1 ms 384 KB Output is correct
12 Correct 912 ms 12752 KB Output is correct
13 Correct 622 ms 13176 KB Output is correct
14 Correct 954 ms 10076 KB Output is correct
15 Correct 1076 ms 9976 KB Output is correct
16 Correct 665 ms 6876 KB Output is correct
17 Correct 959 ms 10104 KB Output is correct
18 Correct 991 ms 9580 KB Output is correct
19 Correct 1559 ms 16004 KB Output is correct
20 Correct 2723 ms 6396 KB Output is correct
21 Correct 357 ms 1308 KB Output is correct
22 Correct 3084 ms 8824 KB Output is correct
23 Correct 316 ms 18424 KB Output is correct
24 Correct 1806 ms 11800 KB Output is correct
25 Correct 3264 ms 18988 KB Output is correct
26 Correct 2730 ms 19064 KB Output is correct
27 Correct 2582 ms 18356 KB Output is correct
28 Correct 1686 ms 251756 KB Output is correct
29 Runtime error 3155 ms 257024 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 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 256 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 1059 ms 12676 KB Output is correct
13 Correct 693 ms 12900 KB Output is correct
14 Correct 1010 ms 10088 KB Output is correct
15 Correct 1108 ms 9768 KB Output is correct
16 Correct 615 ms 6788 KB Output is correct
17 Correct 1048 ms 9848 KB Output is correct
18 Correct 980 ms 9308 KB Output is correct
19 Correct 1513 ms 15804 KB Output is correct
20 Correct 2882 ms 6296 KB Output is correct
21 Correct 367 ms 1144 KB Output is correct
22 Correct 3184 ms 8908 KB Output is correct
23 Correct 309 ms 18268 KB Output is correct
24 Correct 1808 ms 11728 KB Output is correct
25 Correct 3608 ms 18772 KB Output is correct
26 Correct 2681 ms 18836 KB Output is correct
27 Correct 2488 ms 18144 KB Output is correct
28 Correct 1778 ms 251792 KB Output is correct
29 Runtime error 3246 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -