oj.uz

Submission #580204

# Submission time Handle Problem Language Result Execution time Memory
580204 2022-06-20T17:39:30 Z lorenzoferrari Game (IOI13_game) C++17
100 / 100
 4933 ms 63300 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using LL = long long;

constexpr int LIM = 1 << 30;

mt19937 rng{42};

class ImplicitTreap {
private:
  struct treap {
    int x, y;
    int a, b; // closed interval [a, b]
    LL val;
    LL gcd;
    treap* l = nullptr;
    treap* r = nullptr;
    treap() {}
    treap(int x, LL val) : x(x), y(rng()), a(x), b(x), val(val), gcd(val) {}
    ~treap() {
      if (l) delete l;
      if (r) delete r;
    }
  };
  inline void clean(treap* const t) {
    if (t) {
      t->l = t->r = nullptr;
      delete t;
    }
  }

  inline LL gcd(const treap* const t) {
    return t ? t->gcd : 0LL;
  }

  inline void upd(treap* const t) {
    // assume t->l and t->r are already updated
    if (t) {
      t->gcd = __gcd(__gcd(t->val, gcd(t->l)), gcd(t->r));
      t->a = t->l ? t->l->a : t->x;
      t->b = t->r ? t->r->b : t->x;
    }
  }

  void split(treap* const t, const int x, treap*& l, treap*& r) {
    // split t in [-inf, x], [x+1, +inf]
    if (!t) {
      l = r = nullptr;
    } else if (t->x <= x) {
      split(t->r, x, t->r, r); l = t;
    } else {
      split(t->l, x, l, t->l); r = t;
    }
    upd(l);
    upd(r);
  }

  void merge(treap*& t, treap* l, treap* r) {
    if (!l || !r) {
      t = l ? l : r;
    } else if (l->y > r->y) {
      merge(l->r, l->r, r); t = l;
    } else {
      merge(r->l, l, r->l); t = r;
    }
    upd(t);
  }

  void insert(treap*& t, treap* const nw) {
    // assume nw->x is not present in t
    if (!t) {
      t = nw;
    } else if (nw->y > t->y) {
      split(t, nw->x, nw->l, nw->r);
      t = nw;
    } else {
      insert(nw->x <= t->x ? t->l : t->r, nw);
    }
    upd(t);
  }

  void erase(treap*& t, const int x) {
    if (!t) return;
    if (t->x == x) {
      treap* tmp = t;
      merge(t, t->l, t->r);
      clean(tmp);
    } else {
      erase(x <= t->x ? t->l : t->r, x);
    }
    upd(t);
  }

  LL gcd(treap* const t, const int l, const int r) {
    upd(t);
    if (!t || r < t->a || t->b < l) return 0LL;
    if (l <= t->a && t->b <= r) return t->gcd;
    return __gcd(__gcd((l <= t->x && t->x <= r ? t->val : 0LL), gcd(t->l, l, r)), gcd(t->r, l, r));
  }

  // actual treap
  treap* t = nullptr;
public:
  ImplicitTreap() {}
  ~ImplicitTreap() {
    delete t;
  }
  void update(int x, LL val) {
    // set v[x] = val
    erase(t, x);
    insert(t, new treap(x, val));
  }
  LL query(const int l, const int r) {
    // return sum [l, r]
    return gcd(t, l, r);
  }
};

struct st {
  int a, b;
  st * l = nullptr;
  st * r = nullptr;
  ImplicitTreap son;
  st() {}
  st(int a, int b) : a(a), b(b) {}
  ~st() {
    if (l) delete l;
    if (r) delete r;
  }
  friend void st_update(st * const n, const int p, const int q, const LL k) {
    if (p < n->a || n->b < p) return;
    if (n->a == n->b) {
      n->son.update(q, k);
      return;
    }
    // don't update the son if a != b !
    // you can't just overwrite all the values in the same row, like in 1d
    int m = (n->a + n->b) / 2;
    if (p <= m) {
      if (!n->l) n->l = new st(n->a, m);
      st_update(n->l, p, q, k);
    } else {
      if (!n->r) n->r = new st(m+1, n->b);
      st_update(n->r, p, q, k);
    }
    // suppose n->l and n->r are either zero or up to date
    // rebuild n->son properly
    rebuild(n, p, q);
  }
  friend void rebuild(st * const n, const int p, const int q) {
    LL gl = n->l ? n->l->son.query(q, q) : 0LL;
    LL gr = n->r ? n->r->son.query(q, q) : 0LL;
    n->son.update(q, __gcd(gl, gr));
  }
  friend LL st_query(st * n, const int p, const int q, const int u, const int v) {
    if (!n || u < n->a || n->b < p) return 0LL;
    if (p <= n->a && n->b <= u) return n->son.query(q, v);
    return __gcd(st_query(n->l, p, q, u, v), st_query(n->r, p, q, u, v));
  }
};

st * root;

void cleanup() {
  delete root;
}

void init(int r, int c) {
  root = new st(0, r);
  assert(atexit(cleanup) == 0);
}

void update(int p, int q, LL k) {
  st_update(root, p, q, k);
}

long long calculate(int p, int q, int u, int v) {
  return st_query(root, p, q, u, v);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 714 ms 7620 KB Output is correct
5 Correct 335 ms 7884 KB Output is correct
6 Correct 1187 ms 4752 KB Output is correct
7 Correct 1354 ms 4664 KB Output is correct
8 Correct 781 ms 3772 KB Output is correct
9 Correct 1309 ms 4464 KB Output is correct
10 Correct 1191 ms 4076 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1122 ms 9704 KB Output is correct
13 Correct 2173 ms 4428 KB Output is correct
14 Correct 320 ms 1460 KB Output is correct
15 Correct 2272 ms 5584 KB Output is correct
16 Correct 440 ms 7628 KB Output is correct
17 Correct 1531 ms 5424 KB Output is correct
18 Correct 2782 ms 8396 KB Output is correct
19 Correct 2333 ms 8304 KB Output is correct
20 Correct 2401 ms 7860 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 716 ms 7732 KB Output is correct
13 Correct 331 ms 7912 KB Output is correct
14 Correct 1185 ms 4636 KB Output is correct
15 Correct 1315 ms 4520 KB Output is correct
16 Correct 790 ms 3716 KB Output is correct
17 Correct 1321 ms 4568 KB Output is correct
18 Correct 1173 ms 4208 KB Output is correct
19 Correct 1072 ms 9764 KB Output is correct
20 Correct 2150 ms 4456 KB Output is correct
21 Correct 318 ms 1400 KB Output is correct
22 Correct 2356 ms 5340 KB Output is correct
23 Correct 440 ms 7664 KB Output is correct
24 Correct 1564 ms 5440 KB Output is correct
25 Correct 2856 ms 8044 KB Output is correct
26 Correct 2373 ms 8296 KB Output is correct
27 Correct 2214 ms 7632 KB Output is correct
28 Correct 632 ms 29148 KB Output is correct
29 Correct 1727 ms 32164 KB Output is correct
30 Correct 2410 ms 23496 KB Output is correct
31 Correct 2140 ms 18336 KB Output is correct
32 Correct 444 ms 1440 KB Output is correct
33 Correct 669 ms 1804 KB Output is correct
34 Correct 534 ms 29288 KB Output is correct
35 Correct 1833 ms 15868 KB Output is correct
36 Correct 3705 ms 29424 KB Output is correct
37 Correct 3079 ms 29692 KB Output is correct
38 Correct 2941 ms 29180 KB Output is correct
39 Correct 2317 ms 23144 KB Output is correct
40 Correct 1 ms 300 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 690 ms 7612 KB Output is correct
13 Correct 332 ms 7896 KB Output is correct
14 Correct 1167 ms 4652 KB Output is correct
15 Correct 1306 ms 4528 KB Output is correct
16 Correct 788 ms 3828 KB Output is correct
17 Correct 1336 ms 4568 KB Output is correct
18 Correct 1175 ms 4044 KB Output is correct
19 Correct 1061 ms 10028 KB Output is correct
20 Correct 2131 ms 4288 KB Output is correct
21 Correct 319 ms 1372 KB Output is correct
22 Correct 2346 ms 5204 KB Output is correct
23 Correct 467 ms 7752 KB Output is correct
24 Correct 1541 ms 5376 KB Output is correct
25 Correct 2797 ms 8104 KB Output is correct
26 Correct 2390 ms 8260 KB Output is correct
27 Correct 2246 ms 7800 KB Output is correct
28 Correct 628 ms 28992 KB Output is correct
29 Correct 1696 ms 32012 KB Output is correct
30 Correct 2388 ms 23488 KB Output is correct
31 Correct 2155 ms 18088 KB Output is correct
32 Correct 447 ms 1480 KB Output is correct
33 Correct 710 ms 2028 KB Output is correct
34 Correct 535 ms 29188 KB Output is correct
35 Correct 1814 ms 15820 KB Output is correct
36 Correct 3718 ms 29572 KB Output is correct
37 Correct 2827 ms 29652 KB Output is correct
38 Correct 3064 ms 29176 KB Output is correct
39 Correct 946 ms 61124 KB Output is correct
40 Correct 3176 ms 63300 KB Output is correct
41 Correct 4046 ms 48328 KB Output is correct
42 Correct 3611 ms 37036 KB Output is correct
43 Correct 1168 ms 61304 KB Output is correct
44 Correct 765 ms 1660 KB Output is correct
45 Correct 2388 ms 23316 KB Output is correct
46 Correct 4933 ms 61544 KB Output is correct
47 Correct 4798 ms 61552 KB Output is correct
48 Correct 4865 ms 61184 KB Output is correct
49 Correct 1 ms 212 KB Output is correct