oj.uz

Submission #224978

# Submission time Handle Problem Language Result Execution time Memory
224978 2020-04-19T07:35:52 Z T0p_ Game (IOI13_game) C++14
100 / 100
 3504 ms 82424 KB 
#include "game.h"

#define MAXR 1000000000
#define MAXC 1000000000

#include <assert.h>
#include <stddef.h>

long long gcd2(long long X, long long Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }

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

struct layer2_node {
  layer2_node(int low, int high)
      : low(low), high(high), lft(NULL), rht(NULL), value(0LL) {
  }

  int low;
  int high;
  layer2_node* lft;
  layer2_node* rht;
  long long value;
};

struct layer1_node {
  layer1_node() : lft(NULL), rht(NULL), l2(0, MAXC) {
  }

  layer1_node* lft;
  layer1_node* rht;
  layer2_node l2;
};

static layer1_node root;

static void update2(layer2_node* node, int Q, long long K) {
  int low = node->low;
  int high = node->high;
  int mid = (low + high) / 2;
  if(low + 1 == high) {
    /* For leaf nodes we just update the value directly. */
    node->value = K;
    return;
  }

  layer2_node*& tgt = Q < mid ? node->lft : node->rht;
  if(tgt == NULL) {
    /* If there is no node on this side of the tree create a new leaf node
     * containing exactly our update point. */
    tgt = new layer2_node(Q, Q + 1);
    tgt->value = K;
  } else if(tgt->low <= Q && Q < tgt->high) {
    /* If the existing node contains our query point continue inserting there.
     */
    update2(tgt, Q, K);
  } else {
    /* Otherwise traverse down the virtual tree until the side of our query node
     * and the side of the existing node differ.  Create this node and continue
     * updating along it. */
    do {
      (Q < mid ? high : low) = mid;
      mid = (low + high) / 2;
    } while((Q < mid) == (tgt->low < mid));

    layer2_node* nnode = new layer2_node(low, high);
    (tgt->low < mid ? nnode->lft : nnode->rht) = tgt;
    tgt = nnode;

    update2(nnode, Q, K);
  }

  /* Internal nodes get updated as the gcd of its leaves. */
  node->value = gcd2(node->lft ? node->lft->value : 0,
                     node->rht ? node->rht->value : 0);
}

long long query2(layer2_node* nd, int A, int B) {
  /* The same as the level 1 queries except the interval each node represents
   * may skip some levels of the tree so we store them in the node itself. */
  if(nd == NULL || B <= nd->low || nd->high <= A) {
    return 0;
  } else if(A <= nd->low && nd->high <= B) {
    return nd->value;
  }
  return gcd2(query2(nd->lft, A, B), query2(nd->rht, A, B));
}

static void update1(layer1_node* node, int low, int high,
                    int P, int Q, long long K) {
  int mid = (low + high) / 2;

  if(low + 1 == high) {
    update2(&node->l2, Q, K);
  } else {
    layer1_node*& nnode = P < mid ? node->lft : node->rht;
    (P < mid ? high : low) = mid;
    if(nnode == NULL) {
      nnode = new layer1_node();
    }
    update1(nnode, low, high, P, Q, K);

    /* Compute what value to update with. */
    K = gcd2(node->lft ? query2(&node->lft->l2, Q, Q + 1) : 0,
             node->rht ? query2(&node->rht->l2, Q, Q + 1) : 0);
    update2(&node->l2, Q, K);
  }
}

long long query1(layer1_node* nd, int low, int high,
                 int A1, int B1, int A2, int B2) {
  /* Scan down the tree short-circuiting when we reach a node that contains
   * our entire query interval and combining the result of the level2 queries.
   */
  if(nd == NULL || B1 <= low || high <= A1) {
    return 0;
  } else if(A1 <= low && high <= B1) {
    return query2(&nd->l2, A2, B2);
  }
  int mid = (low + high) / 2;
  return gcd2(query1(nd->lft, low, mid, A1, B1, A2, B2),
              query1(nd->rht, mid, high, A1, B1, A2, B2));
}

void init(int R, int C) {
}

void update(int P, int Q, long long K) {
  update1(&root, 0, MAXR, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query1(&root, 0, MAXR, P, U + 1, Q, 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 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 436 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 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 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 856 ms 31984 KB Output is correct
5 Correct 580 ms 32408 KB Output is correct
6 Correct 931 ms 29304 KB Output is correct
7 Correct 1008 ms 28920 KB Output is correct
8 Correct 569 ms 15480 KB Output is correct
9 Correct 1014 ms 28920 KB Output is correct
10 Correct 989 ms 28624 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 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 5 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 892 ms 13784 KB Output is correct
13 Correct 1354 ms 7008 KB Output is correct
14 Correct 387 ms 1144 KB Output is correct
15 Correct 1564 ms 9720 KB Output is correct
16 Correct 433 ms 13688 KB Output is correct
17 Correct 1039 ms 9632 KB Output is correct
18 Correct 2071 ms 14152 KB Output is correct
19 Correct 1646 ms 14340 KB Output is correct
20 Correct 1567 ms 13624 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 5 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 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 830 ms 32040 KB Output is correct
13 Correct 609 ms 32224 KB Output is correct
14 Correct 926 ms 29080 KB Output is correct
15 Correct 1035 ms 29060 KB Output is correct
16 Correct 591 ms 15480 KB Output is correct
17 Correct 1016 ms 28892 KB Output is correct
18 Correct 1059 ms 28664 KB Output is correct
19 Correct 928 ms 13684 KB Output is correct
20 Correct 1335 ms 7032 KB Output is correct
21 Correct 379 ms 1016 KB Output is correct
22 Correct 1577 ms 9648 KB Output is correct
23 Correct 425 ms 13692 KB Output is correct
24 Correct 931 ms 9668 KB Output is correct
25 Correct 1677 ms 14260 KB Output is correct
26 Correct 1402 ms 14404 KB Output is correct
27 Correct 1311 ms 13560 KB Output is correct
28 Correct 526 ms 43512 KB Output is correct
29 Correct 1379 ms 45432 KB Output is correct
30 Correct 2561 ms 35384 KB Output is correct
31 Correct 2318 ms 28848 KB Output is correct
32 Correct 436 ms 10360 KB Output is correct
33 Correct 526 ms 10812 KB Output is correct
34 Correct 303 ms 39160 KB Output is correct
35 Correct 969 ms 27060 KB Output is correct
36 Correct 1984 ms 43668 KB Output is correct
37 Correct 1524 ms 43488 KB Output is correct
38 Correct 1514 ms 43028 KB Output is correct
39 Correct 1270 ms 35960 KB Output is correct
40 Correct 4 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 798 ms 32020 KB Output is correct
13 Correct 544 ms 32248 KB Output is correct
14 Correct 837 ms 29152 KB Output is correct
15 Correct 916 ms 28988 KB Output is correct
16 Correct 564 ms 15608 KB Output is correct
17 Correct 877 ms 29048 KB Output is correct
18 Correct 862 ms 28716 KB Output is correct
19 Correct 873 ms 13592 KB Output is correct
20 Correct 1298 ms 7156 KB Output is correct
21 Correct 380 ms 1008 KB Output is correct
22 Correct 1491 ms 9720 KB Output is correct
23 Correct 396 ms 13688 KB Output is correct
24 Correct 864 ms 9592 KB Output is correct
25 Correct 1889 ms 14148 KB Output is correct
26 Correct 1520 ms 14248 KB Output is correct
27 Correct 1375 ms 13656 KB Output is correct
28 Correct 532 ms 43384 KB Output is correct
29 Correct 1391 ms 45424 KB Output is correct
30 Correct 2488 ms 35576 KB Output is correct
31 Correct 2252 ms 28920 KB Output is correct
32 Correct 419 ms 10548 KB Output is correct
33 Correct 546 ms 10744 KB Output is correct
34 Correct 299 ms 39160 KB Output is correct
35 Correct 951 ms 27128 KB Output is correct
36 Correct 1968 ms 43340 KB Output is correct
37 Correct 1563 ms 43744 KB Output is correct
38 Correct 1520 ms 43000 KB Output is correct
39 Correct 664 ms 81272 KB Output is correct
40 Correct 2218 ms 82424 KB Output is correct
41 Correct 3504 ms 67284 KB Output is correct
42 Correct 3179 ms 52684 KB Output is correct
43 Correct 528 ms 76920 KB Output is correct
44 Correct 514 ms 10744 KB Output is correct
45 Correct 1230 ms 35808 KB Output is correct
46 Correct 2614 ms 80988 KB Output is correct
47 Correct 2653 ms 81124 KB Output is correct
48 Correct 2469 ms 80760 KB Output is correct
49 Correct 4 ms 256 KB Output is correct