oj.uz

Submission #531875

# Submission time Handle Problem Language Result Execution time Memory
531875 2022-03-01T19:02:03 Z Alex_tz307 Game (IOI13_game) C++17
100 / 100
 7271 ms 56904 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

const int mod = 1e9 + 9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treapNode {
  treapNode* l;
  treapNode* r;
  int key, prior;
  int64_t val, gcd;
};

using ptr = treapNode*;
using pt = pair<ptr, ptr>;
ptr NIL = new treapNode{nullptr, nullptr, 0, -1, 0, 0};

int64_t gcd2(int64_t X, int64_t Y) {
  int64_t tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

void updateNode(ptr &x) {
  if (x != NIL) {
    x->gcd = gcd2(gcd2(x->l->gcd, x->val), x->r->gcd);
  }
}

pt split(ptr &x, int k) {
  if (x == NIL) {
    return {NIL, NIL};
  }
  if (k < x->key) {
    pt p = split(x->l, k);
    x->l = p.second;
    updateNode(x);
    return {p.first, x};
  }
  pt p = split(x->r, k);
  x->r = p.first;
  updateNode(x);
  return {x, p.second};
}

ptr join(ptr x, ptr y) {
  if (x == NIL) {
    return y;
  }
  if (y == NIL) {
    return x;
  }
  if (y->prior < x->prior) {
    x->r = join(x->r, y);
    updateNode(x);
    return x;
  }
  y->l = join(x, y->l);
  updateNode(y);
  return y;
}

bool check(ptr &x, int k, int64_t v) {
  if (x == NIL) {
    return false;
  }
  if (x->key == k) {
    x->val = v;
    updateNode(x);
    return true;
  }
  if (k < x->key) {
    bool ret = check(x->l, k, v);
    updateNode(x);
    return ret;
  } else {
    bool ret = check(x->r, k, v);
    updateNode(x);
    return ret;
  }
}

ptr ins(ptr &x, int k, int64_t v) {
  if (check(x, k, v)) {
    return x;
  }
  pt p = split(x, k);
  ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
  return join(join(p.first, newNode), p.second);
}

int64_t queryY(ptr &x, int st, int dr) {
  pt p1 = split(x, st - 1);
  pt p2 = split(p1.second, dr);
  int64_t ans = p2.first->gcd;
  p1.second = join(p2.first, p2.second);
  x = join(p1.first, p1.second);
  return ans;
}

struct sgtNode {
  ptr root;
  sgtNode* l;
  sgtNode* r;

  sgtNode() : root(NIL), l(nullptr), r(nullptr) {}
} *root;

void update(sgtNode* &x, int lx, int rx, int X, int Y, int64_t v) {
  if (!x) {
    x = new sgtNode();
  }
  x->root = ins(x->root, Y, v);
  if (lx == rx) {
    return;
  }
  int mid = (lx + rx) / 2;
  if (X <= mid) {
    update(x->l, lx, mid, X, Y, v);
  } else {
    update(x->r, mid + 1, rx, X, Y, v);
  }
  int64_t gcd = 0;
  if (x->l) {
    gcd = queryY(x->l->root, Y, Y);
  }
  if (x->r) {
    gcd = gcd2(gcd, queryY(x->r->root, Y, Y));
  }
  ins(x->root, Y, gcd);
}

int64_t queryX(sgtNode* &x, int lx, int rx, int x1, int x2, int y1, int y2) {
  if (!x) {
    return 0;
  }
  if (x1 <= lx && rx <= x2) {
    return queryY(x->root, y1, y2);
  }
  int mid = (lx + rx) / 2;
  int64_t ans = 0;
  if (x1 <= mid) {
    ans = gcd2(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));
  }
  if (mid < x2) {
    ans = gcd2(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));
  }
  return ans;
}

int N;

void init(int R, int C) {
  N = R;
}

void update(int P, int Q, long long K) {
  update(root, 0, N - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return queryX(root, 0, N - 1, P, U, Q, V);
}

Compilation message

game.cpp: In function 'treapNode* ins(treapNode*&, int, int64_t)':
game.cpp:94:50: warning: narrowing conversion of '(rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % ((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((int)mod)))' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   94 |   ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
      |                                            ~~~~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1044 ms 10816 KB Output is correct
5 Correct 430 ms 10488 KB Output is correct
6 Correct 1478 ms 8008 KB Output is correct
7 Correct 1593 ms 7676 KB Output is correct
8 Correct 1095 ms 7084 KB Output is correct
9 Correct 1599 ms 7796 KB Output is correct
10 Correct 1334 ms 7496 KB Output is correct
11 Correct 1 ms 292 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1403 ms 12076 KB Output is correct
13 Correct 3294 ms 6956 KB Output is correct
14 Correct 425 ms 5448 KB Output is correct
15 Correct 3570 ms 8188 KB Output is correct
16 Correct 523 ms 9836 KB Output is correct
17 Correct 1981 ms 8820 KB Output is correct
18 Correct 3307 ms 11280 KB Output is correct
19 Correct 2865 ms 11424 KB Output is correct
20 Correct 2772 ms 10780 KB Output is correct
21 Correct 1 ms 296 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 903 ms 10776 KB Output is correct
13 Correct 422 ms 10716 KB Output is correct
14 Correct 1343 ms 8188 KB Output is correct
15 Correct 1508 ms 7808 KB Output is correct
16 Correct 988 ms 7148 KB Output is correct
17 Correct 1461 ms 7928 KB Output is correct
18 Correct 1224 ms 7548 KB Output is correct
19 Correct 1374 ms 12096 KB Output is correct
20 Correct 3137 ms 7056 KB Output is correct
21 Correct 426 ms 5448 KB Output is correct
22 Correct 3443 ms 8032 KB Output is correct
23 Correct 502 ms 9828 KB Output is correct
24 Correct 1952 ms 8924 KB Output is correct
25 Correct 3302 ms 11176 KB Output is correct
26 Correct 2877 ms 11496 KB Output is correct
27 Correct 2723 ms 10704 KB Output is correct
28 Correct 1083 ms 31388 KB Output is correct
29 Correct 1922 ms 34184 KB Output is correct
30 Correct 4285 ms 23924 KB Output is correct
31 Correct 3662 ms 20440 KB Output is correct
32 Correct 573 ms 10140 KB Output is correct
33 Correct 876 ms 10756 KB Output is correct
34 Correct 760 ms 28064 KB Output is correct
35 Correct 2232 ms 21408 KB Output is correct
36 Correct 4673 ms 32004 KB Output is correct
37 Correct 3768 ms 32168 KB Output is correct
38 Correct 3736 ms 31592 KB Output is correct
39 Correct 3170 ms 27072 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 276 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 984 ms 10868 KB Output is correct
13 Correct 460 ms 10708 KB Output is correct
14 Correct 1445 ms 8032 KB Output is correct
15 Correct 1636 ms 7780 KB Output is correct
16 Correct 1062 ms 7048 KB Output is correct
17 Correct 1597 ms 7932 KB Output is correct
18 Correct 1363 ms 7412 KB Output is correct
19 Correct 1438 ms 12108 KB Output is correct
20 Correct 3239 ms 6988 KB Output is correct
21 Correct 454 ms 5448 KB Output is correct
22 Correct 3644 ms 8096 KB Output is correct
23 Correct 575 ms 9964 KB Output is correct
24 Correct 2135 ms 8912 KB Output is correct
25 Correct 3645 ms 11204 KB Output is correct
26 Correct 3187 ms 11368 KB Output is correct
27 Correct 2874 ms 10820 KB Output is correct
28 Correct 1131 ms 31452 KB Output is correct
29 Correct 2189 ms 34024 KB Output is correct
30 Correct 4533 ms 23912 KB Output is correct
31 Correct 3974 ms 20092 KB Output is correct
32 Correct 601 ms 10184 KB Output is correct
33 Correct 914 ms 10308 KB Output is correct
34 Correct 849 ms 27784 KB Output is correct
35 Correct 2452 ms 21372 KB Output is correct
36 Correct 4761 ms 31956 KB Output is correct
37 Correct 3744 ms 32120 KB Output is correct
38 Correct 3673 ms 31524 KB Output is correct
39 Correct 1699 ms 54872 KB Output is correct
40 Correct 3716 ms 56904 KB Output is correct
41 Correct 7271 ms 42656 KB Output is correct
42 Correct 6331 ms 34176 KB Output is correct
43 Correct 1697 ms 51600 KB Output is correct
44 Correct 1002 ms 10532 KB Output is correct
45 Correct 3145 ms 27116 KB Output is correct
46 Correct 6390 ms 55648 KB Output is correct
47 Correct 6343 ms 55720 KB Output is correct
48 Correct 6941 ms 55224 KB Output is correct
49 Correct 1 ms 204 KB Output is correct