oj.uz

Submission #98126

# Submission time Handle Problem Language Result Execution time Memory
98126 2019-02-20T23:25:29 Z MiricaMatei Game (IOI13_game) C++14
80 / 100
 13000 ms 63336 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 K) {
  if (root == emptyTree)
    root = new SegTree {emptyTreap, emptyTree, emptyTree};
  root->treap = TreapUpdate(root->treap, coord(P, Q), 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 (root == emptyTree)
    return 0;
  if (P <= l && r <= U)
    return TreapQuery(root->treap, coord(P, Q), coord(U, V));
  if (U < l)
    return 0;
  if (r < P)
    return 0;
  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) {
  Root = SegTreeUpdate(Root, 1, N, 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);
}

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 4 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 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 2 ms 384 KB Output is correct
11 Correct 4 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 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1348 ms 7548 KB Output is correct
5 Correct 629 ms 7800 KB Output is correct
6 Correct 2471 ms 4632 KB Output is correct
7 Correct 2954 ms 4376 KB Output is correct
8 Correct 1775 ms 3856 KB Output is correct
9 Correct 2971 ms 4492 KB Output is correct
10 Correct 2416 ms 4088 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 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 384 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 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2106 ms 11672 KB Output is correct
13 Correct 8576 ms 8420 KB Output is correct
14 Correct 1233 ms 8880 KB Output is correct
15 Correct 8876 ms 9180 KB Output is correct
16 Correct 727 ms 9264 KB Output is correct
17 Correct 4002 ms 5808 KB Output is correct
18 Correct 7988 ms 9556 KB Output is correct
19 Correct 6256 ms 9616 KB Output is correct
20 Correct 5857 ms 9136 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 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 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 356 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 2 ms 384 KB Output is correct
12 Correct 1489 ms 7628 KB Output is correct
13 Correct 585 ms 7924 KB Output is correct
14 Correct 2475 ms 4728 KB Output is correct
15 Correct 2971 ms 4384 KB Output is correct
16 Correct 1798 ms 3840 KB Output is correct
17 Correct 2762 ms 4456 KB Output is correct
18 Correct 2266 ms 4132 KB Output is correct
19 Correct 2167 ms 11800 KB Output is correct
20 Correct 8413 ms 8584 KB Output is correct
21 Correct 1227 ms 8876 KB Output is correct
22 Correct 9668 ms 9180 KB Output is correct
23 Correct 670 ms 9232 KB Output is correct
24 Correct 4226 ms 5840 KB Output is correct
25 Correct 8344 ms 9668 KB Output is correct
26 Correct 6919 ms 9704 KB Output is correct
27 Correct 6451 ms 9080 KB Output is correct
28 Correct 2439 ms 26524 KB Output is correct
29 Correct 3570 ms 35436 KB Output is correct
30 Correct 11196 ms 29912 KB Output is correct
31 Correct 9768 ms 29416 KB Output is correct
32 Correct 1632 ms 26884 KB Output is correct
33 Correct 2443 ms 26992 KB Output is correct
34 Correct 912 ms 32488 KB Output is correct
35 Correct 4772 ms 20708 KB Output is correct
36 Correct 9147 ms 32848 KB Output is correct
37 Correct 7455 ms 32888 KB Output is correct
38 Correct 7386 ms 32380 KB Output is correct
39 Correct 6386 ms 26852 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 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 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 1543 ms 7424 KB Output is correct
13 Correct 558 ms 7932 KB Output is correct
14 Correct 2566 ms 4600 KB Output is correct
15 Correct 2825 ms 4436 KB Output is correct
16 Correct 1930 ms 3768 KB Output is correct
17 Correct 2968 ms 4420 KB Output is correct
18 Correct 2360 ms 4068 KB Output is correct
19 Correct 2353 ms 11800 KB Output is correct
20 Correct 8801 ms 8416 KB Output is correct
21 Correct 1202 ms 8892 KB Output is correct
22 Correct 8809 ms 9196 KB Output is correct
23 Correct 828 ms 9176 KB Output is correct
24 Correct 4197 ms 5964 KB Output is correct
25 Correct 8109 ms 9336 KB Output is correct
26 Correct 6483 ms 9696 KB Output is correct
27 Correct 6717 ms 9080 KB Output is correct
28 Correct 2357 ms 26180 KB Output is correct
29 Correct 3645 ms 35072 KB Output is correct
30 Correct 10625 ms 29860 KB Output is correct
31 Correct 10422 ms 29076 KB Output is correct
32 Correct 1853 ms 26496 KB Output is correct
33 Correct 2553 ms 26616 KB Output is correct
34 Correct 799 ms 32380 KB Output is correct
35 Correct 5221 ms 20368 KB Output is correct
36 Correct 9522 ms 32644 KB Output is correct
37 Correct 8034 ms 32732 KB Output is correct
38 Correct 8290 ms 32148 KB Output is correct
39 Correct 3601 ms 61212 KB Output is correct
40 Correct 5869 ms 63336 KB Output is correct
41 Execution timed out 13080 ms 52612 KB Time limit exceeded
42 Halted 0 ms 0 KB -