oj.uz

Submission #98275

# Submission time Handle Problem Language Result Execution time Memory
98275 2019-02-21T18:50:56 Z MiricaMatei Game (IOI13_game) C++14
100 / 100
 8907 ms 67380 KB 
#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

# 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 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

# 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 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

# 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 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

# 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 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

# 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 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