oj.uz

Submission #98201

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

Node1D* update2(Node1D* root, Node1D* root1, Node1D* root2, int l, int r, int q, long long val, bool ok) {
  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, q, val, ok);
  } 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, q, val, ok);
  }
  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, int p, int q, long long val) {
  if (root == empty2)
    root = new Node2D {empty1, empty2, empty2};
  if (l == r) {
    root->root = update2(root->root, root->left->root, root->right->root, 1, M, q, val, 0);
    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);
  root->root = update2(root->root, root->left->root, root->right->root,  1, M, q, val, 1);
  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 3 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 256 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 3 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 920 ms 14096 KB Output is correct
5 Correct 730 ms 14572 KB Output is correct
6 Correct 889 ms 11452 KB Output is correct
7 Correct 1000 ms 11240 KB Output is correct
8 Correct 603 ms 8320 KB Output is correct
9 Correct 1032 ms 11232 KB Output is correct
10 Correct 1012 ms 10908 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 3 ms 384 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 128 KB Output is correct
8 Correct 3 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 3 ms 384 KB Output is correct
12 Correct 1548 ms 17452 KB Output is correct
13 Correct 2740 ms 7780 KB Output is correct
14 Correct 390 ms 2544 KB Output is correct
15 Correct 2854 ms 10392 KB Output is correct
16 Correct 288 ms 19888 KB Output is correct
17 Correct 1801 ms 13108 KB Output is correct
18 Correct 3252 ms 20120 KB Output is correct
19 Correct 2953 ms 20208 KB Output is correct
20 Correct 2500 ms 19900 KB Output is correct
21 Correct 3 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 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 3 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 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 842 ms 14324 KB Output is correct
13 Correct 678 ms 14584 KB Output is correct
14 Correct 999 ms 11560 KB Output is correct
15 Correct 1012 ms 11284 KB Output is correct
16 Correct 629 ms 8376 KB Output is correct
17 Correct 1010 ms 11300 KB Output is correct
18 Correct 975 ms 10904 KB Output is correct
19 Correct 1458 ms 17536 KB Output is correct
20 Correct 2629 ms 7892 KB Output is correct
21 Correct 451 ms 2564 KB Output is correct
22 Correct 3299 ms 10468 KB Output is correct
23 Correct 303 ms 19832 KB Output is correct
24 Correct 1728 ms 13152 KB Output is correct
25 Correct 3462 ms 20284 KB Output is correct
26 Correct 2900 ms 20304 KB Output is correct
27 Correct 2749 ms 19704 KB Output is correct
28 Correct 1700 ms 254664 KB Output is correct
29 Runtime error 3680 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 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 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 2 ms 384 KB Output is correct
12 Correct 782 ms 14200 KB Output is correct
13 Correct 657 ms 14684 KB Output is correct
14 Correct 856 ms 11580 KB Output is correct
15 Correct 1054 ms 11288 KB Output is correct
16 Correct 680 ms 8464 KB Output is correct
17 Correct 1063 ms 11556 KB Output is correct
18 Correct 912 ms 11052 KB Output is correct
19 Correct 1553 ms 17560 KB Output is correct
20 Correct 2898 ms 8044 KB Output is correct
21 Correct 419 ms 2696 KB Output is correct
22 Correct 3173 ms 10480 KB Output is correct
23 Correct 332 ms 19940 KB Output is correct
24 Correct 1807 ms 13148 KB Output is correct
25 Correct 3198 ms 20292 KB Output is correct
26 Correct 2754 ms 20432 KB Output is correct
27 Correct 2658 ms 20036 KB Output is correct
28 Correct 1719 ms 254836 KB Output is correct
29 Runtime error 3503 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -