답안 #2621 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2621	2013-07-28T02:51:54 Z	model_code	게임 (IOI13_game)	C++	100 / 100	7860 ms	70640 KB

game

#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

#	결과	메모리	Grader output
1	Correct	1208 KB	Output is correct
2	Correct	1340 KB	Output is correct
3	Correct	1340 KB	Output is correct
4	Correct	1208 KB	Output is correct
5	Correct	1208 KB	Output is correct
6	Correct	1340 KB	Output is correct
7	Correct	1208 KB	Output is correct
8	Correct	1208 KB	Output is correct
9	Correct	1340 KB	Output is correct
10	Correct	1208 KB	Output is correct
11	Correct	1340 KB	Output is correct
12	Correct	1208 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #2621

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0