oj.uz

Submission #2621

# Submission time Handle Problem Language Result Execution time Memory
2621 2013-07-28T02:51:54 Z model_code Game (IOI13_game) C++
100 / 100
 7860 ms 70640 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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1340 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1340 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1340 KB Output is correct
12 Correct 0 ms 1208 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 1264 ms 28796 KB Output is correct
5 Correct 836 ms 28664 KB Output is correct
6 Correct 1436 ms 28796 KB Output is correct
7 Correct 1512 ms 28796 KB Output is correct
8 Correct 884 ms 14672 KB Output is correct
9 Correct 1500 ms 28664 KB Output is correct
10 Correct 1368 ms 28796 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1340 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1340 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1340 KB Output is correct
12 Correct 1312 ms 10316 KB Output is correct
13 Correct 2668 ms 7148 KB Output is correct
14 Correct 484 ms 1340 KB Output is correct
15 Correct 3016 ms 9656 KB Output is correct
16 Correct 600 ms 13748 KB Output is correct
17 Correct 1476 ms 9128 KB Output is correct
18 Correct 2584 ms 13748 KB Output is correct
19 Correct 2184 ms 13748 KB Output is correct
20 Correct 2016 ms 13748 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1340 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1340 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1340 KB Output is correct
12 Correct 1212 ms 28796 KB Output is correct
13 Correct 808 ms 28664 KB Output is correct
14 Correct 1372 ms 28796 KB Output is correct
15 Correct 1532 ms 28796 KB Output is correct
16 Correct 880 ms 14672 KB Output is correct
17 Correct 1496 ms 28664 KB Output is correct
18 Correct 1324 ms 28796 KB Output is correct
19 Correct 1320 ms 10316 KB Output is correct
20 Correct 2648 ms 7148 KB Output is correct
21 Correct 476 ms 1340 KB Output is correct
22 Correct 3044 ms 9656 KB Output is correct
23 Correct 592 ms 13748 KB Output is correct
24 Correct 1480 ms 9128 KB Output is correct
25 Correct 2612 ms 13748 KB Output is correct
26 Correct 2240 ms 13748 KB Output is correct
27 Correct 1964 ms 13748 KB Output is correct
28 Correct 620 ms 32888 KB Output is correct
29 Correct 2080 ms 32492 KB Output is correct
30 Correct 5652 ms 28532 KB Output is correct
31 Correct 5000 ms 21668 KB Output is correct
32 Correct 560 ms 1340 KB Output is correct
33 Correct 752 ms 1868 KB Output is correct
34 Correct 360 ms 32492 KB Output is correct
35 Correct 1500 ms 16652 KB Output is correct
36 Correct 2740 ms 32492 KB Output is correct
37 Correct 2212 ms 32492 KB Output is correct
38 Correct 2112 ms 32492 KB Output is correct
39 Correct 1892 ms 24968 KB Output is correct
40 Correct 0 ms 1208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1340 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1340 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1340 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1340 KB Output is correct
12 Correct 1224 ms 28796 KB Output is correct
13 Correct 792 ms 28664 KB Output is correct
14 Correct 1376 ms 28796 KB Output is correct
15 Correct 1492 ms 28796 KB Output is correct
16 Correct 864 ms 14672 KB Output is correct
17 Correct 1464 ms 28664 KB Output is correct
18 Correct 1316 ms 28796 KB Output is correct
19 Correct 1284 ms 10316 KB Output is correct
20 Correct 2636 ms 7148 KB Output is correct
21 Correct 488 ms 1340 KB Output is correct
22 Correct 3080 ms 9656 KB Output is correct
23 Correct 592 ms 13748 KB Output is correct
24 Correct 1480 ms 9128 KB Output is correct
25 Correct 2684 ms 13748 KB Output is correct
26 Correct 2284 ms 13748 KB Output is correct
27 Correct 1992 ms 13748 KB Output is correct
28 Correct 636 ms 32888 KB Output is correct
29 Correct 2080 ms 32492 KB Output is correct
30 Correct 5596 ms 28532 KB Output is correct
31 Correct 5024 ms 21668 KB Output is correct
32 Correct 560 ms 1340 KB Output is correct
33 Correct 748 ms 1868 KB Output is correct
34 Correct 380 ms 32492 KB Output is correct
35 Correct 1468 ms 16652 KB Output is correct
36 Correct 2788 ms 32492 KB Output is correct
37 Correct 2220 ms 32492 KB Output is correct
38 Correct 2132 ms 32492 KB Output is correct
39 Correct 864 ms 70640 KB Output is correct
40 Correct 3440 ms 69584 KB Output is correct
41 Correct 7860 ms 59948 KB Output is correct
42 Correct 7200 ms 45296 KB Output is correct
43 Correct 732 ms 69584 KB Output is correct
44 Correct 708 ms 1472 KB Output is correct
45 Correct 1956 ms 24968 KB Output is correct
46 Correct 3640 ms 69584 KB Output is correct
47 Correct 3628 ms 69584 KB Output is correct
48 Correct 3376 ms 69584 KB Output is correct
49 Correct 0 ms 1208 KB Output is correct