oj.uz

Submission #43170

# Submission time Handle Problem Language Result Execution time Memory
43170 2018-03-09T17:13:24 Z yusufake Game (IOI13_game) C++
100 / 100
 6084 ms 256000 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 1 ms 248 KB Output is correct
2 Correct 4 ms 608 KB Output is correct
3 Correct 4 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 4 ms 832 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 2 ms 832 KB Output is correct
9 Correct 3 ms 832 KB Output is correct
10 Correct 2 ms 832 KB Output is correct
11 Correct 2 ms 880 KB Output is correct
12 Correct 1 ms 880 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 880 KB Output is correct
2 Correct 1 ms 880 KB Output is correct
3 Correct 2 ms 880 KB Output is correct
4 Correct 1061 ms 36824 KB Output is correct
5 Correct 703 ms 41116 KB Output is correct
6 Correct 1540 ms 42488 KB Output is correct
7 Correct 1402 ms 46964 KB Output is correct
8 Correct 796 ms 46964 KB Output is correct
9 Correct 1392 ms 55972 KB Output is correct
10 Correct 1174 ms 60408 KB Output is correct
11 Correct 2 ms 60408 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 60408 KB Output is correct
2 Correct 4 ms 60408 KB Output is correct
3 Correct 4 ms 60408 KB Output is correct
4 Correct 1 ms 60408 KB Output is correct
5 Correct 1 ms 60408 KB Output is correct
6 Correct 4 ms 60408 KB Output is correct
7 Correct 1 ms 60408 KB Output is correct
8 Correct 2 ms 60408 KB Output is correct
9 Correct 3 ms 60408 KB Output is correct
10 Correct 2 ms 60408 KB Output is correct
11 Correct 2 ms 60408 KB Output is correct
12 Correct 1123 ms 60408 KB Output is correct
13 Correct 2337 ms 60408 KB Output is correct
14 Correct 439 ms 60408 KB Output is correct
15 Correct 2608 ms 60408 KB Output is correct
16 Correct 481 ms 66868 KB Output is correct
17 Correct 1376 ms 67644 KB Output is correct
18 Correct 2491 ms 77276 KB Output is correct
19 Correct 2123 ms 82852 KB Output is correct
20 Correct 1866 ms 87516 KB Output is correct
21 Correct 1 ms 87516 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 87516 KB Output is correct
2 Correct 3 ms 87516 KB Output is correct
3 Correct 3 ms 87516 KB Output is correct
4 Correct 2 ms 87516 KB Output is correct
5 Correct 1 ms 87516 KB Output is correct
6 Correct 3 ms 87516 KB Output is correct
7 Correct 1 ms 87516 KB Output is correct
8 Correct 2 ms 87516 KB Output is correct
9 Correct 3 ms 87516 KB Output is correct
10 Correct 2 ms 87516 KB Output is correct
11 Correct 2 ms 87516 KB Output is correct
12 Correct 1042 ms 110216 KB Output is correct
13 Correct 700 ms 114508 KB Output is correct
14 Correct 1359 ms 116112 KB Output is correct
15 Correct 1373 ms 120460 KB Output is correct
16 Correct 820 ms 120460 KB Output is correct
17 Correct 1421 ms 129364 KB Output is correct
18 Correct 1243 ms 133868 KB Output is correct
19 Correct 1197 ms 133868 KB Output is correct
20 Correct 2364 ms 133868 KB Output is correct
21 Correct 434 ms 133868 KB Output is correct
22 Correct 2741 ms 133868 KB Output is correct
23 Correct 518 ms 140176 KB Output is correct
24 Correct 1401 ms 141176 KB Output is correct
25 Correct 2522 ms 150672 KB Output is correct
26 Correct 2085 ms 156452 KB Output is correct
27 Correct 1925 ms 161128 KB Output is correct
28 Correct 665 ms 190628 KB Output is correct
29 Correct 1755 ms 203384 KB Output is correct
30 Correct 4208 ms 203384 KB Output is correct
31 Correct 3935 ms 203892 KB Output is correct
32 Correct 521 ms 203892 KB Output is correct
33 Correct 696 ms 203892 KB Output is correct
34 Correct 361 ms 239536 KB Output is correct
35 Correct 1415 ms 239536 KB Output is correct
36 Correct 2783 ms 256000 KB Output is correct
37 Correct 2238 ms 256000 KB Output is correct
38 Correct 2256 ms 256000 KB Output is correct
39 Correct 1899 ms 256000 KB Output is correct
40 Correct 2 ms 256000 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256000 KB Output is correct
2 Correct 3 ms 256000 KB Output is correct
3 Correct 4 ms 256000 KB Output is correct
4 Correct 1 ms 256000 KB Output is correct
5 Correct 1 ms 256000 KB Output is correct
6 Correct 3 ms 256000 KB Output is correct
7 Correct 2 ms 256000 KB Output is correct
8 Correct 1 ms 256000 KB Output is correct
9 Correct 3 ms 256000 KB Output is correct
10 Correct 2 ms 256000 KB Output is correct
11 Correct 2 ms 256000 KB Output is correct
12 Correct 1010 ms 256000 KB Output is correct
13 Correct 685 ms 256000 KB Output is correct
14 Correct 1316 ms 256000 KB Output is correct
15 Correct 1347 ms 256000 KB Output is correct
16 Correct 777 ms 256000 KB Output is correct
17 Correct 1432 ms 256000 KB Output is correct
18 Correct 1209 ms 256000 KB Output is correct
19 Correct 1150 ms 256000 KB Output is correct
20 Correct 2351 ms 256000 KB Output is correct
21 Correct 451 ms 256000 KB Output is correct
22 Correct 2735 ms 256000 KB Output is correct
23 Correct 492 ms 256000 KB Output is correct
24 Correct 1770 ms 256000 KB Output is correct
25 Correct 2779 ms 256000 KB Output is correct
26 Correct 2358 ms 256000 KB Output is correct
27 Correct 1926 ms 256000 KB Output is correct
28 Correct 684 ms 256000 KB Output is correct
29 Correct 1826 ms 256000 KB Output is correct
30 Correct 4423 ms 256000 KB Output is correct
31 Correct 4005 ms 256000 KB Output is correct
32 Correct 507 ms 256000 KB Output is correct
33 Correct 725 ms 256000 KB Output is correct
34 Correct 392 ms 256000 KB Output is correct
35 Correct 1451 ms 256000 KB Output is correct
36 Correct 3000 ms 256000 KB Output is correct
37 Correct 2320 ms 256000 KB Output is correct
38 Correct 2139 ms 256000 KB Output is correct
39 Correct 883 ms 256000 KB Output is correct
40 Correct 3014 ms 256000 KB Output is correct
41 Correct 6084 ms 256000 KB Output is correct
42 Correct 5712 ms 256000 KB Output is correct
43 Correct 761 ms 256000 KB Output is correct
44 Correct 654 ms 256000 KB Output is correct
45 Correct 1915 ms 256000 KB Output is correct
46 Correct 3935 ms 256000 KB Output is correct
47 Correct 4109 ms 256000 KB Output is correct
48 Correct 3809 ms 256000 KB Output is correct
49 Correct 2 ms 256000 KB Output is correct