답안 #98275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98275	2019-02-21T18:50:56 Z	MiricaMatei	게임 (IOI13_game)	C++14	100 / 100	8907 ms	67380 KB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int N, M;
long long inf;

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

long long coord(int x, int y) {
  return 1LL * (y - 1) * N + x;
}

struct Treap {
  Treap* left;
  Treap* right;
  long long prio, pos, val, gcd;
};

Treap* emptyTreap = new Treap {NULL, NULL, 0LL, 0LL, 0LL, 0LL};

void recompute(Treap* root) {
  if (root != emptyTreap)
    root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val);
}

pair<Treap*, Treap*> split(Treap* root, long long pos) {
  if (root == emptyTreap)
    return {emptyTreap, emptyTreap};
  pair<Treap*, Treap*> ans;
  if (root->pos <= pos) {
    ans.first = root;
    pair<Treap*, Treap*>aux = split(root->right, pos);
    ans.second = aux.second;
    ans.first->right = aux.first;
    recompute(ans.first);
  } else {
    ans.second = root;
    pair<Treap*, Treap*>aux = split(root->left, pos);
    ans.first = aux.first;
    ans.second->left = aux.second;
    recompute(ans.second);
  }
  return ans;
}

Treap* join(Treap* a, Treap* b) {
  if (a == emptyTreap)
    return b;
  if (b == emptyTreap)
    return a;
  if (a->prio < b->prio) {
    a->right = join(a->right, b);
    recompute(a);
    return a;
  } else {
    b->left = join(a, b->left);
    recompute(b);
    return b;
  }
}

Treap* TreapUpdate(Treap* root, long long pos, long long val) {
  pair<Treap*, Treap*>aux1 = split(root, pos - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos);
  Treap* newTreap = new Treap {emptyTreap, emptyTreap, ((long long)rand() << 31) ^ rand(), pos, val, val};
  return join(join(aux1.first, newTreap), aux2.second);
}

long long TreapQuery(Treap* root, long long l, long long r, long long p, long long q) {
  if (root == emptyTreap)
    return 0;
  long long ans = 0;
  if (p <= root->pos && root->pos <= q) {
    ans = root->val;
    if (l >= p)
      ans = gcd2(ans, root->left->gcd);
    else
      ans = gcd2(ans, TreapQuery(root->left, l, root->pos, p, q));
    if (r <= q)
      ans = gcd2(ans, root->right->gcd);
    else
      ans = gcd2(ans, TreapQuery(root->right, root->pos, r, p, q));
  } else {
    if (p > root->pos)
      ans = TreapQuery(root->right, root->pos, r, p, q);
    else
      ans = TreapQuery(root->left, l, root->pos, p, q);
  }
  return ans;

}

struct SegTree {
  Treap* treap;
  SegTree* left;
  SegTree* right;
};

SegTree* emptyTree = new SegTree {emptyTreap, NULL, NULL};
SegTree* Root;


SegTree* SegTreeUpdate(SegTree* root, int l, int r, int P, int Q, long long pos, long long K) {
  if (root == emptyTree)
    root = new SegTree {emptyTreap, emptyTree, emptyTree};
  root->treap = TreapUpdate(root->treap, pos, K);
  if (l == r)
    return root;
  int mid = (l + r) / 2;
  if (P <= mid)
    root->left = SegTreeUpdate(root->left, l, mid, P, Q, pos, K);
  else
    root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, pos, K);
  return root;
}

long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V, long long pos1, long long pos2) {
  if (U < l)
    return 0;
  if (r < P)
    return 0;
  if (root == emptyTree)
    return 0;
  if (P <= l && r <= U)
    return TreapQuery(root->treap, 0, inf, pos1, pos2);
  int mid = (l + r) / 2;
  return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V, pos1, pos2), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V, pos1, pos2));
}

void init(int R, int C) {
  srand(time(NULL));
  Root = emptyTree;
  N = R;
  M = C;
  inf = coord(N, M) + 1;
}

void update(int P, int Q, long long K) {
  Root = SegTreeUpdate(Root, 1, N, P + 1, Q + 1, coord(P + 1, Q + 1), K);
}

long long calculate(int P, int Q, int U, int V) {
  return SegTreeQuery(Root, 1, N, P + 1, Q + 1, U + 1, V + 1, coord(P + 1, Q + 1), coord(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

#	결과	실행 시간	메모리	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	256 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	955 ms	9076 KB	Output is correct
5	Correct	598 ms	8964 KB	Output is correct
6	Correct	1029 ms	5916 KB	Output is correct
7	Correct	1286 ms	5596 KB	Output is correct
8	Correct	646 ms	4856 KB	Output is correct
9	Correct	1152 ms	5672 KB	Output is correct
10	Correct	1188 ms	5240 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 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	256 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	356 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	1704 ms	12804 KB	Output is correct
13	Correct	3303 ms	9588 KB	Output is correct
14	Correct	683 ms	10028 KB	Output is correct
15	Correct	3571 ms	10184 KB	Output is correct
16	Correct	736 ms	10232 KB	Output is correct
17	Correct	1532 ms	7296 KB	Output is correct
18	Correct	3648 ms	11472 KB	Output is correct
19	Correct	2568 ms	11676 KB	Output is correct
20	Correct	2958 ms	11064 KB	Output is correct
21	Correct	2 ms	256 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	947 ms	8696 KB	Output is correct
13	Correct	581 ms	8840 KB	Output is correct
14	Correct	1020 ms	6008 KB	Output is correct
15	Correct	1260 ms	5772 KB	Output is correct
16	Correct	637 ms	4828 KB	Output is correct
17	Correct	1255 ms	5880 KB	Output is correct
18	Correct	1310 ms	5372 KB	Output is correct
19	Correct	1661 ms	12808 KB	Output is correct
20	Correct	3440 ms	9596 KB	Output is correct
21	Correct	742 ms	10076 KB	Output is correct
22	Correct	3447 ms	10200 KB	Output is correct
23	Correct	753 ms	10204 KB	Output is correct
24	Correct	1637 ms	7172 KB	Output is correct
25	Correct	3353 ms	11544 KB	Output is correct
26	Correct	2946 ms	11628 KB	Output is correct
27	Correct	3480 ms	11064 KB	Output is correct
28	Correct	1617 ms	31196 KB	Output is correct
29	Correct	2622 ms	38660 KB	Output is correct
30	Correct	5097 ms	29964 KB	Output is correct
31	Correct	4740 ms	29504 KB	Output is correct
32	Correct	1285 ms	29304 KB	Output is correct
33	Correct	1631 ms	29176 KB	Output is correct
34	Correct	788 ms	32360 KB	Output is correct
35	Correct	1964 ms	23680 KB	Output is correct
36	Correct	4673 ms	36688 KB	Output is correct
37	Correct	3591 ms	36628 KB	Output is correct
38	Correct	4078 ms	36232 KB	Output is correct
39	Correct	2764 ms	30840 KB	Output is correct
40	Correct	2 ms	256 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	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	332 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	914 ms	8520 KB	Output is correct
13	Correct	597 ms	8800 KB	Output is correct
14	Correct	1064 ms	5752 KB	Output is correct
15	Correct	1250 ms	5368 KB	Output is correct
16	Correct	587 ms	4728 KB	Output is correct
17	Correct	1226 ms	5500 KB	Output is correct
18	Correct	1110 ms	5084 KB	Output is correct
19	Correct	1770 ms	12728 KB	Output is correct
20	Correct	3060 ms	9492 KB	Output is correct
21	Correct	746 ms	9852 KB	Output is correct
22	Correct	3347 ms	10292 KB	Output is correct
23	Correct	851 ms	9984 KB	Output is correct
24	Correct	1670 ms	6980 KB	Output is correct
25	Correct	3168 ms	11224 KB	Output is correct
26	Correct	2437 ms	11392 KB	Output is correct
27	Correct	2831 ms	10764 KB	Output is correct
28	Correct	1422 ms	31444 KB	Output is correct
29	Correct	2473 ms	39132 KB	Output is correct
30	Correct	5638 ms	30116 KB	Output is correct
31	Correct	4905 ms	29780 KB	Output is correct
32	Correct	1347 ms	29504 KB	Output is correct
33	Correct	1590 ms	29316 KB	Output is correct
34	Correct	628 ms	32760 KB	Output is correct
35	Correct	2121 ms	23900 KB	Output is correct
36	Correct	4559 ms	37020 KB	Output is correct
37	Correct	3704 ms	36968 KB	Output is correct
38	Correct	3827 ms	36416 KB	Output is correct
39	Correct	2122 ms	65660 KB	Output is correct
40	Correct	4086 ms	67380 KB	Output is correct
41	Correct	8907 ms	57356 KB	Output is correct
42	Correct	7864 ms	55608 KB	Output is correct
43	Correct	1567 ms	62528 KB	Output is correct
44	Correct	2815 ms	53136 KB	Output is correct
45	Correct	2851 ms	30884 KB	Output is correct
46	Correct	6367 ms	66572 KB	Output is correct
47	Correct	6121 ms	66636 KB	Output is correct
48	Correct	6621 ms	66120 KB	Output is correct
49	Correct	2 ms	256 KB	Output is correct