oj.uz

Submission #967334

# Submission time Handle Problem Language Result Execution time Memory
967334 2024-04-22T02:24:37 Z obokaman Game (IOI13_game) C++17
100 / 100
 4171 ms 65652 KB 
#include <iostream>
#include <vector>
#include <string>
#include "game.h"

using namespace std;

typedef long long ll;

struct Node {
  Node *l, *r;
  int x;
  ll val;
  int prio;
  ll gcd;
};

ll gcd(Node* t) {
  return t ? t->gcd : -1;
}
ll val(Node* t) {
  return t ? t->val : -1;
}
ll gcdrec(ll a, ll b) {
  return a == 0 ? b : gcdrec(b%a, a); 
}
ll gcd(ll a, ll b) {
  if (a == -1 || b == -1) return a == -1 ? b : a;
  return gcdrec(a, b);
}

Node* init_node(int x, ll val) {
  Node* t = new Node;
  t->l = t->r = nullptr;
  t->x = x;
  t->val = t->gcd = val;
  t->prio = rand();
  return t;
}
void update(Node* t) {
  if (t) {
    t->gcd = gcd(gcd(gcd(t->l), t->val), gcd(t->r));
  }
}
void split(Node* t, Node*& l, Node*& r, int x) {
  if (!t) {
    l = r = nullptr;
  } else {
    if (x < t->x) {
      r = t;
      split(t->l, l, t->l, x);
    } else {
      l = t;
      split(t->r, t->r, r, x);
    }
    update(t);
  }
}
void merge(Node*& t, Node* l, Node* r) {
  if (!l || !r) {
    t = l ? l : r;
  } else {
    if (l->prio > r->prio) {
      t = l;
      merge(t->r, t->r, r);
    } else {
      t = r;
      merge(t->l, l, t->l);
    }
    update(t);
  } 
}
void update_x(Node*& t, int x, ll val) {
  Node* t1, *t2, *t3;
  split(t, t1, t2, x-1);
  split(t2, t2, t3, x);
  if (!t2) t2 = init_node(x, val);
  else t2->val = t2->gcd = val;
  merge(t, t1, t2);
  merge(t, t, t3);
}
ll gcdRS(Node* t, int R, int S) {
  Node* t1, *t2, *t3;
  split(t, t1, t2, R-1);
  split(t2, t2, t3, S);
  ll res = gcd(t2);
  merge(t, t1, t2);
  merge(t, t, t3);
  return res;
}
ll find_gcd(Node* t, int Q) {
  if (!t) return -1;
  if (t->x == Q) return t->val;
  else {
    return find_gcd(Q < t->x ? t->l : t->r, Q);
  }
}

struct SSTNode {
  SSTNode *l = nullptr, *r = nullptr;
  Node* row = nullptr;
};
Node* row(SSTNode* t) {
  return t ? t->row : nullptr;
}
// t is [a, b), x \in [a,b)
void set(SSTNode*& t, int P, int Q, ll val, int a, int b) {
  if (!t) t = new SSTNode;
  if (b > a+1) {
    int m = (a+b)/2;
    if (P < m) set(t->l, P, Q, val, a, m);
    else set(t->r, P, Q, val, m, b);
    // Update row, using that most gcd are not expected to change.
    Node* t1, *t2, *t3;
    split(t->row, t1, t2, Q-1);
    split(t2, t2, t3, Q);
    ll new_gcd = gcd(val, gcd(find_gcd(row(t->l), Q), find_gcd(row(t->r), Q)));
    if (!t2) {
      t2 = init_node(Q, new_gcd);
    } else {
      t2->val = t2->gcd = new_gcd;
    }
    merge(t->row, t1, t2);
    merge(t->row, t->row, t3);
  } else {
    update_x(t->row, Q, val);
  }
}
// gcd of [P, Q]x[R, S], knowing that t covers [a,b)
ll query(SSTNode* t, int P, int Q, int R, int S, int a, int b) {
  if (!t || Q < a || P >= b || a >= b) return -1;
  if (P <= a && b-1 <= Q) {
    ll res = gcdRS(t->row, R, S);
    return res;
  } else {
    ll m = (a+b)/2;
    ll res = gcd(query(t->l, P, Q, R, S, a, m),
		 query(t->r, P, Q, R, S, m, b));
    return res;
  }
}

SSTNode* gn = nullptr;
int globalRows = -1;
int Rp2 = 1;

void init(int R, int C) {
  globalRows = R;
  while (Rp2 <= R) Rp2*=2;
}
void update(int P, int Q, ll K) {
  set(gn, P, Q, K, 0, Rp2);
}
ll calculate(int P, int Q, int R, int S) {
  ll res = query(gn, P, R, Q, S, 0, Rp2);
  return res == -1 ? 0 : res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 571 ms 11532 KB Output is correct
5 Correct 264 ms 11128 KB Output is correct
6 Correct 924 ms 8332 KB Output is correct
7 Correct 1063 ms 8112 KB Output is correct
8 Correct 701 ms 6984 KB Output is correct
9 Correct 1086 ms 8104 KB Output is correct
10 Correct 956 ms 7888 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 480 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 974 ms 12664 KB Output is correct
13 Correct 2036 ms 7448 KB Output is correct
14 Correct 294 ms 4872 KB Output is correct
15 Correct 2221 ms 8636 KB Output is correct
16 Correct 658 ms 10984 KB Output is correct
17 Correct 1536 ms 8792 KB Output is correct
18 Correct 2531 ms 11876 KB Output is correct
19 Correct 2155 ms 11860 KB Output is correct
20 Correct 2126 ms 11508 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 581 ms 11316 KB Output is correct
13 Correct 312 ms 11236 KB Output is correct
14 Correct 946 ms 8324 KB Output is correct
15 Correct 1075 ms 8412 KB Output is correct
16 Correct 734 ms 6860 KB Output is correct
17 Correct 1018 ms 8092 KB Output is correct
18 Correct 943 ms 7652 KB Output is correct
19 Correct 934 ms 12628 KB Output is correct
20 Correct 2009 ms 7132 KB Output is correct
21 Correct 323 ms 4688 KB Output is correct
22 Correct 2143 ms 8920 KB Output is correct
23 Correct 654 ms 10736 KB Output is correct
24 Correct 1486 ms 8600 KB Output is correct
25 Correct 2561 ms 11776 KB Output is correct
26 Correct 2223 ms 12072 KB Output is correct
27 Correct 2158 ms 11384 KB Output is correct
28 Correct 813 ms 34292 KB Output is correct
29 Correct 1528 ms 36952 KB Output is correct
30 Correct 2801 ms 26840 KB Output is correct
31 Correct 2289 ms 22028 KB Output is correct
32 Correct 430 ms 8216 KB Output is correct
33 Correct 630 ms 8528 KB Output is correct
34 Correct 1155 ms 31568 KB Output is correct
35 Correct 1648 ms 21796 KB Output is correct
36 Correct 3002 ms 35180 KB Output is correct
37 Correct 2538 ms 35268 KB Output is correct
38 Correct 2469 ms 34408 KB Output is correct
39 Correct 2051 ms 28808 KB Output is correct
40 Correct 1 ms 600 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 432 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 579 ms 11432 KB Output is correct
13 Correct 277 ms 11236 KB Output is correct
14 Correct 935 ms 8824 KB Output is correct
15 Correct 1114 ms 8096 KB Output is correct
16 Correct 728 ms 6944 KB Output is correct
17 Correct 1036 ms 8000 KB Output is correct
18 Correct 964 ms 7824 KB Output is correct
19 Correct 961 ms 12864 KB Output is correct
20 Correct 2039 ms 7008 KB Output is correct
21 Correct 293 ms 4688 KB Output is correct
22 Correct 2123 ms 8352 KB Output is correct
23 Correct 626 ms 10732 KB Output is correct
24 Correct 1512 ms 8720 KB Output is correct
25 Correct 2578 ms 12020 KB Output is correct
26 Correct 2131 ms 12128 KB Output is correct
27 Correct 2137 ms 11784 KB Output is correct
28 Correct 761 ms 34248 KB Output is correct
29 Correct 1373 ms 37260 KB Output is correct
30 Correct 2647 ms 27060 KB Output is correct
31 Correct 2295 ms 22984 KB Output is correct
32 Correct 410 ms 9512 KB Output is correct
33 Correct 642 ms 9808 KB Output is correct
34 Correct 1180 ms 31260 KB Output is correct
35 Correct 1678 ms 21808 KB Output is correct
36 Correct 3263 ms 35096 KB Output is correct
37 Correct 2525 ms 35244 KB Output is correct
38 Correct 2646 ms 34368 KB Output is correct
39 Correct 1124 ms 63716 KB Output is correct
40 Correct 2567 ms 65648 KB Output is correct
41 Correct 3932 ms 51064 KB Output is correct
42 Correct 3644 ms 40832 KB Output is correct
43 Correct 1500 ms 62212 KB Output is correct
44 Correct 616 ms 9920 KB Output is correct
45 Correct 2162 ms 30200 KB Output is correct
46 Correct 4171 ms 65652 KB Output is correct
47 Correct 4109 ms 65616 KB Output is correct
48 Correct 4170 ms 65516 KB Output is correct
49 Correct 1 ms 344 KB Output is correct