oj.uz

Submission #98128

# Submission time Handle Problem Language Result Execution time Memory
98128 2019-02-20T23:37:11 Z MiricaMatei Game (IOI13_game) C++14
80 / 100
 13000 ms 57288 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int N, M;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && 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;
  int prio;
  long long pos, val, gcd;
};

Treap* emptyTreap = new Treap {NULL, NULL, 0, 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, rand(), pos, val, val};
  return join(join(aux1.first, newTreap), aux2.second);
}

long long TreapQuery(Treap* root, long long pos1, long long pos2) {
  pair<Treap*, Treap*>aux1 = split(root, pos1 - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos2);
  long long answer = 0;
  if (aux2.first != emptyTreap)
    answer = aux2.first->gcd;
  root = join(join(aux1.first, aux2.first), aux2.second);
  return answer;
}

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, 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;
}

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

# Verdict Execution time Memory 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 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 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 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1465 ms 7452 KB Output is correct
5 Correct 613 ms 7776 KB Output is correct
6 Correct 2451 ms 4708 KB Output is correct
7 Correct 2849 ms 4384 KB Output is correct
8 Correct 1784 ms 3704 KB Output is correct
9 Correct 2960 ms 4472 KB Output is correct
10 Correct 2408 ms 4048 KB Output is correct
11 Correct 3 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 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 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 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 2299 ms 11724 KB Output is correct
13 Correct 8854 ms 8520 KB Output is correct
14 Correct 1227 ms 8796 KB Output is correct
15 Correct 9224 ms 9164 KB Output is correct
16 Correct 876 ms 9184 KB Output is correct
17 Correct 4663 ms 5736 KB Output is correct
18 Correct 8557 ms 9476 KB Output is correct
19 Correct 6696 ms 9664 KB Output is correct
20 Correct 6421 ms 9056 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 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 1415 ms 7580 KB Output is correct
13 Correct 669 ms 7640 KB Output is correct
14 Correct 2495 ms 4672 KB Output is correct
15 Correct 2961 ms 4480 KB Output is correct
16 Correct 1835 ms 3572 KB Output is correct
17 Correct 2890 ms 4468 KB Output is correct
18 Correct 2319 ms 4004 KB Output is correct
19 Correct 2162 ms 11656 KB Output is correct
20 Correct 8098 ms 8496 KB Output is correct
21 Correct 1231 ms 8700 KB Output is correct
22 Correct 9654 ms 9176 KB Output is correct
23 Correct 1141 ms 9080 KB Output is correct
24 Correct 4171 ms 5944 KB Output is correct
25 Correct 8223 ms 9568 KB Output is correct
26 Correct 6262 ms 9572 KB Output is correct
27 Correct 6393 ms 9080 KB Output is correct
28 Correct 2172 ms 26488 KB Output is correct
29 Correct 3462 ms 29388 KB Output is correct
30 Correct 11706 ms 23744 KB Output is correct
31 Correct 9415 ms 23304 KB Output is correct
32 Correct 1586 ms 20704 KB Output is correct
33 Correct 2985 ms 20980 KB Output is correct
34 Correct 887 ms 26472 KB Output is correct
35 Correct 4848 ms 14752 KB Output is correct
36 Correct 9455 ms 26824 KB Output is correct
37 Correct 7569 ms 27044 KB Output is correct
38 Correct 7555 ms 26396 KB Output is correct
39 Correct 6669 ms 21044 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 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 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 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 1511 ms 7420 KB Output is correct
13 Correct 503 ms 7788 KB Output is correct
14 Correct 2483 ms 4672 KB Output is correct
15 Correct 3032 ms 4316 KB Output is correct
16 Correct 1839 ms 3604 KB Output is correct
17 Correct 2791 ms 4476 KB Output is correct
18 Correct 2281 ms 4192 KB Output is correct
19 Correct 2134 ms 11524 KB Output is correct
20 Correct 8443 ms 8336 KB Output is correct
21 Correct 1208 ms 8704 KB Output is correct
22 Correct 9179 ms 9132 KB Output is correct
23 Correct 750 ms 9052 KB Output is correct
24 Correct 4191 ms 5624 KB Output is correct
25 Correct 8418 ms 9248 KB Output is correct
26 Correct 6526 ms 9460 KB Output is correct
27 Correct 5901 ms 9120 KB Output is correct
28 Correct 2259 ms 26540 KB Output is correct
29 Correct 3229 ms 29408 KB Output is correct
30 Correct 11619 ms 23736 KB Output is correct
31 Correct 9924 ms 23296 KB Output is correct
32 Correct 1665 ms 20792 KB Output is correct
33 Correct 2590 ms 20740 KB Output is correct
34 Correct 702 ms 26432 KB Output is correct
35 Correct 4980 ms 14636 KB Output is correct
36 Correct 9446 ms 26744 KB Output is correct
37 Correct 7585 ms 27020 KB Output is correct
38 Correct 7396 ms 26488 KB Output is correct
39 Correct 2998 ms 55472 KB Output is correct
40 Correct 5928 ms 57288 KB Output is correct
41 Execution timed out 13042 ms 47704 KB Time limit exceeded
42 Halted 0 ms 0 KB -