oj.uz

Submission #98129

# Submission time Handle Problem Language Result Execution time Memory
98129 2019-02-20T23:47:50 Z MiricaMatei Game (IOI13_game) C++14
80 / 100
 13000 ms 57072 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;
}

long long pos, pos1, pos2;

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

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

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

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

long long calculate(int P, int Q, int U, int V) {
  pos1 = coord(P + 1, Q + 1);
  pos2 = coord(U + 1, V + 1);
  return SegTreeQuery(Root, 1, N, P + 1, Q + 1, 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 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 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 2 ms 384 KB Output is correct
4 Correct 1434 ms 7128 KB Output is correct
5 Correct 565 ms 7404 KB Output is correct
6 Correct 2469 ms 4376 KB Output is correct
7 Correct 2998 ms 4088 KB Output is correct
8 Correct 1864 ms 3356 KB Output is correct
9 Correct 2660 ms 4216 KB Output is correct
10 Correct 2340 ms 3656 KB Output is correct
11 Correct 2 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 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 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2114 ms 11484 KB Output is correct
13 Correct 8360 ms 8128 KB Output is correct
14 Correct 1037 ms 8508 KB Output is correct
15 Correct 9200 ms 8760 KB Output is correct
16 Correct 724 ms 8768 KB Output is correct
17 Correct 4129 ms 5484 KB Output is correct
18 Correct 8138 ms 9364 KB Output is correct
19 Correct 6548 ms 9372 KB Output is correct
20 Correct 6096 ms 8728 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 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 4 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 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 1480 ms 7104 KB Output is correct
13 Correct 581 ms 7416 KB Output is correct
14 Correct 2475 ms 4316 KB Output is correct
15 Correct 2928 ms 3944 KB Output is correct
16 Correct 1858 ms 3260 KB Output is correct
17 Correct 2794 ms 4196 KB Output is correct
18 Correct 2380 ms 3828 KB Output is correct
19 Correct 2347 ms 11528 KB Output is correct
20 Correct 8621 ms 8128 KB Output is correct
21 Correct 1114 ms 8472 KB Output is correct
22 Correct 9027 ms 8876 KB Output is correct
23 Correct 616 ms 8824 KB Output is correct
24 Correct 4468 ms 5400 KB Output is correct
25 Correct 8183 ms 9180 KB Output is correct
26 Correct 6531 ms 9276 KB Output is correct
27 Correct 6571 ms 8804 KB Output is correct
28 Correct 2343 ms 26024 KB Output is correct
29 Correct 3324 ms 29128 KB Output is correct
30 Correct 11360 ms 23516 KB Output is correct
31 Correct 10288 ms 22904 KB Output is correct
32 Correct 1985 ms 20316 KB Output is correct
33 Correct 2847 ms 20484 KB Output is correct
34 Correct 769 ms 26080 KB Output is correct
35 Correct 4993 ms 14308 KB Output is correct
36 Correct 9774 ms 26512 KB Output is correct
37 Correct 7398 ms 26420 KB Output is correct
38 Correct 7391 ms 25844 KB Output is correct
39 Correct 6302 ms 20836 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 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 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 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 1483 ms 7160 KB Output is correct
13 Correct 587 ms 7416 KB Output is correct
14 Correct 2450 ms 4364 KB Output is correct
15 Correct 2823 ms 4120 KB Output is correct
16 Correct 1834 ms 3384 KB Output is correct
17 Correct 2901 ms 4136 KB Output is correct
18 Correct 2078 ms 3800 KB Output is correct
19 Correct 2168 ms 11328 KB Output is correct
20 Correct 8683 ms 8144 KB Output is correct
21 Correct 1151 ms 8500 KB Output is correct
22 Correct 9034 ms 8824 KB Output is correct
23 Correct 795 ms 8824 KB Output is correct
24 Correct 4424 ms 5636 KB Output is correct
25 Correct 8431 ms 9160 KB Output is correct
26 Correct 7328 ms 9308 KB Output is correct
27 Correct 6406 ms 8804 KB Output is correct
28 Correct 2245 ms 25828 KB Output is correct
29 Correct 3285 ms 29076 KB Output is correct
30 Correct 10874 ms 23364 KB Output is correct
31 Correct 9386 ms 22884 KB Output is correct
32 Correct 1646 ms 20380 KB Output is correct
33 Correct 2879 ms 20452 KB Output is correct
34 Correct 679 ms 26000 KB Output is correct
35 Correct 4801 ms 14120 KB Output is correct
36 Correct 9394 ms 26564 KB Output is correct
37 Correct 7285 ms 26692 KB Output is correct
38 Correct 7234 ms 25972 KB Output is correct
39 Correct 3067 ms 55084 KB Output is correct
40 Correct 5596 ms 57072 KB Output is correct
41 Execution timed out 13006 ms 48048 KB Time limit exceeded
42 Halted 0 ms 0 KB -