oj.uz

Submission #98130

# Submission time Handle Problem Language Result Execution time Memory
98130 2019-02-21T00:03:12 Z MiricaMatei Game (IOI13_game) C++17
80 / 100
 13000 ms 57216 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 ( 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 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 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 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 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 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 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2021 ms 7280 KB Output is correct
5 Correct 886 ms 7500 KB Output is correct
6 Correct 2420 ms 4196 KB Output is correct
7 Correct 2945 ms 4188 KB Output is correct
8 Correct 1852 ms 3520 KB Output is correct
9 Correct 2785 ms 4088 KB Output is correct
10 Correct 2551 ms 3816 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 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 3 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 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 3618 ms 11356 KB Output is correct
13 Correct 8554 ms 8160 KB Output is correct
14 Correct 1175 ms 8568 KB Output is correct
15 Correct 9516 ms 8788 KB Output is correct
16 Correct 819 ms 8876 KB Output is correct
17 Correct 4418 ms 5452 KB Output is correct
18 Correct 8596 ms 9168 KB Output is correct
19 Correct 6797 ms 9196 KB Output is correct
20 Correct 6750 ms 8644 KB Output is correct
21 Correct 3 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 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 1950 ms 7188 KB Output is correct
13 Correct 915 ms 7544 KB Output is correct
14 Correct 2776 ms 4400 KB Output is correct
15 Correct 3158 ms 3948 KB Output is correct
16 Correct 1765 ms 3436 KB Output is correct
17 Correct 2820 ms 4048 KB Output is correct
18 Correct 2486 ms 3804 KB Output is correct
19 Correct 3320 ms 11328 KB Output is correct
20 Correct 8286 ms 8096 KB Output is correct
21 Correct 1142 ms 8452 KB Output is correct
22 Correct 9527 ms 8840 KB Output is correct
23 Correct 806 ms 8872 KB Output is correct
24 Correct 4437 ms 5600 KB Output is correct
25 Correct 8637 ms 9108 KB Output is correct
26 Correct 6772 ms 9208 KB Output is correct
27 Correct 6563 ms 8760 KB Output is correct
28 Correct 2313 ms 26104 KB Output is correct
29 Correct 4856 ms 29068 KB Output is correct
30 Correct 10956 ms 23332 KB Output is correct
31 Correct 10764 ms 23056 KB Output is correct
32 Correct 1684 ms 20564 KB Output is correct
33 Correct 2754 ms 20504 KB Output is correct
34 Correct 919 ms 26204 KB Output is correct
35 Correct 4739 ms 14440 KB Output is correct
36 Correct 9273 ms 26508 KB Output is correct
37 Correct 7318 ms 26696 KB Output is correct
38 Correct 7622 ms 25988 KB Output is correct
39 Correct 6153 ms 20796 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 384 KB Output is correct
5 Correct 2 ms 384 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 1982 ms 7280 KB Output is correct
13 Correct 1008 ms 7472 KB Output is correct
14 Correct 2587 ms 4300 KB Output is correct
15 Correct 3226 ms 4092 KB Output is correct
16 Correct 1933 ms 3268 KB Output is correct
17 Correct 2720 ms 4172 KB Output is correct
18 Correct 2405 ms 3668 KB Output is correct
19 Correct 3148 ms 11424 KB Output is correct
20 Correct 8528 ms 8072 KB Output is correct
21 Correct 1200 ms 8492 KB Output is correct
22 Correct 9606 ms 8892 KB Output is correct
23 Correct 683 ms 8696 KB Output is correct
24 Correct 4442 ms 5612 KB Output is correct
25 Correct 8252 ms 9328 KB Output is correct
26 Correct 6634 ms 9264 KB Output is correct
27 Correct 6749 ms 8752 KB Output is correct
28 Correct 2406 ms 25976 KB Output is correct
29 Correct 3980 ms 28876 KB Output is correct
30 Correct 11718 ms 23464 KB Output is correct
31 Correct 10242 ms 23000 KB Output is correct
32 Correct 1790 ms 20352 KB Output is correct
33 Correct 2569 ms 20476 KB Output is correct
34 Correct 906 ms 26232 KB Output is correct
35 Correct 4737 ms 14380 KB Output is correct
36 Correct 9857 ms 26376 KB Output is correct
37 Correct 7506 ms 26648 KB Output is correct
38 Correct 7638 ms 25832 KB Output is correct
39 Correct 2976 ms 54996 KB Output is correct
40 Correct 7144 ms 57216 KB Output is correct
41 Execution timed out 13064 ms 47224 KB Time limit exceeded
42 Halted 0 ms 0 KB -