Submission #967313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967313	2024-04-21T20:18:00 Z	obokaman	Game (IOI13_game)	C++17	100 / 100	4411 ms	134736 KB

game

#include <iostream>
#include <vector>
#include <string>
#include "game.h"

using namespace std;

bool safecheck = false;
typedef long long ll;

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

struct RowNode {
  RowNode *l, *r;
  int x;
  Node* row;
  Node* thick_row;
  int prio;
};

Node* row(RowNode* t) {
  return t ? t->row : nullptr;
}

Node* thick_row(RowNode* t) {
  return t ? t->thick_row : nullptr;
}

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));
  }
}

// x in l
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;
}


// gcd([x, \infy))
ll queryR(RowNode* t, int x, int R, int S) {
  if (!t) return -1;
  else if (x < t->x) {
    return gcd(gcdRS(thick_row(t->r), R, S),
	       gcd(gcdRS(row(t), R, S), queryR(t->l, x, R, S)));
  } else if (x == t->x) {
    return gcd(gcdRS(thick_row(t->r), R, S), gcdRS(row(t), R, S));
  } else return queryR(t->r, x, R, S);
}

// gcd((-\infy, x])
ll queryL(RowNode* t, int x, int R, int S) {
  if (!t) return -1;
  else if (x > t->x) {
    return gcd(gcdRS(thick_row(t->l), R, S),
	       gcd(gcdRS(row(t), R, S), queryL(t->r, x, R, S)));
  } else if (x == t->x) {
    return gcd(gcdRS(thick_row(t->l), R, S),
	       gcdRS(row(t), R, S));
  } else return queryL(t->l, x, R, S);
}

// gcd of [P, Q]x[R, S]
ll query(RowNode* t, int P, int Q, int R, int S) {
  if (!t) return -1;
  if (t->x < P) return query(t->r, P, Q, R, S);
  else if (t->x > Q) return query(t->l, P, Q, R, S);
  else {
    return gcd(gcdRS(row(t), R, S), gcd(queryR(t->l, P, R, S), queryL(t->r, Q, R, S)));
  }
}

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);
  }
}

void pointUpdateThickrow(RowNode*& t, int Q) {
  // We don't need to fully recalculate thickrow, because only x=Q had
  // changed.
  Node* t1, *t2, *t3;
  split(t->thick_row, t1, t2, Q-1);
  split(t2, t2, t3, Q);
  ll newval = gcd( find_gcd(thick_row(t->l), Q),
		   gcd( find_gcd(thick_row(t->r), Q), find_gcd(t->row, Q)) );
  if (!t2) t2 = init_node(Q, newval);
  else t2->val = t2->gcd = newval;

  merge(t->thick_row, t1, t2);
  merge(t->thick_row, t->thick_row, t3);      
}

RowNode* find(RowNode* t, int P) {
  if (!t) {
    return nullptr;
  }
  else if (P < t->x) {
    return find(t->l, P);
  }
  else if (P > t->x) {
    return find(t->r, P);
  }
  else {
    return t;
  }
}

void copy(Node* src, Node*& dst) {
  if (!src) dst = nullptr;
  else {
    dst = new Node;
    copy(src->l, dst->l);
    copy(src->r, dst->r);
    dst->x = src->x;
    dst->val = src->val;
    dst->prio = src->prio;
    dst->gcd = src->gcd;
  }
}

Node* join(Node* t1, Node* t2) {
  Node* t;
  if (!t1 && !t2) t = nullptr;
  else if (!t1) copy(t2, t);
  else if (!t2) copy(t1, t);
  else {
    if (t1->prio < t2->prio) swap(t1, t2);
    t = new Node;
    Node* t2l, *t2x, *t2r;
    ll t2gcd = gcd(t2);
    split(t2, t2l, t2x, t1->x-1);
    split(t2x, t2x, t2r, t1->x);
    t->x = t1->x;
    t->val = gcd(val(t1), val(t2x));
    t->gcd = gcd(gcd(t1), t2gcd);
    t->prio = t1->prio;
    t->l = join(t1->l, t2l);
    t->r = join(t1->r, t2r);
    merge(t2, t2l, t2x);
    merge(t2, t2, t2r);
  }
  return t;
}

// P in l.
void split(RowNode* t, RowNode*& l, RowNode*& r, int P) {
  if (!t) {
    l = r = nullptr;
  } else {
    if (P < t->x) {
      r = t;
      split(t->l, l, t->l, P); 
    } else {
      l = t;
      split(t->r, t->r, r, P);
    }
    t->thick_row = join(join(thick_row(t->l), t->row), thick_row(t->r));
  }
}

void set_rec(RowNode*& t, int P, int Q, ll val, int prio) {
  if (!t) {
    t = new RowNode;
    t->l = t->r = nullptr;
    t->x = P;
    t->row = init_node(Q, val);
    t->prio = prio;
  } else {
    if (prio > t->prio) {
      // prio > 0 means we won't find P.
      RowNode* child = t;
      t = new RowNode;
      t->x = P;
      split(child, t->l, t->r, P);
      t->row = init_node(Q, val);
      // (Q,val) will be updated as part of pointUpdateThickrow
      t->thick_row = join(thick_row(t->l), thick_row(t->r));
      t->prio = prio;
    } else {
      if (P < t->x) set_rec(t->l, P, Q, val, prio);
      else if (P == t->x) update_x(t->row, Q, val);
      else set_rec(t->r, P, Q, val, prio);
    }
  }
  pointUpdateThickrow(t, Q);
}

void set(RowNode*& t, int P, int Q, ll val) {
  set_rec(t, P, Q, val, find(t, P) ? 0 : rand());
}


RowNode* globalt = nullptr;

void init(int R, int C) {
}
void update(int P, int Q, ll K) {
  set(globalt, P, Q, K);
}
ll calculate(int P, int Q, int R, int S) {
  ll res = query(globalt, P, R, Q, S);
  return res == -1 ? 0 : res;
}

//#include "game.h"

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	552 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	440 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	432 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	931 ms	11524 KB	Output is correct
5	Correct	343 ms	11208 KB	Output is correct
6	Correct	1252 ms	8532 KB	Output is correct
7	Correct	1517 ms	8256 KB	Output is correct
8	Correct	994 ms	7452 KB	Output is correct
9	Correct	1477 ms	9252 KB	Output is correct
10	Correct	1346 ms	8092 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	464 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	516 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	436 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	941 ms	16660 KB	Output is correct
13	Correct	2124 ms	10804 KB	Output is correct
14	Correct	457 ms	5736 KB	Output is correct
15	Correct	3055 ms	14164 KB	Output is correct
16	Correct	1881 ms	19056 KB	Output is correct
17	Correct	1731 ms	15256 KB	Output is correct
18	Correct	3431 ms	19668 KB	Output is correct
19	Correct	2544 ms	20388 KB	Output is correct
20	Correct	2989 ms	19664 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	1 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	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	887 ms	11468 KB	Output is correct
13	Correct	345 ms	11436 KB	Output is correct
14	Correct	1251 ms	8784 KB	Output is correct
15	Correct	1526 ms	8680 KB	Output is correct
16	Correct	990 ms	7548 KB	Output is correct
17	Correct	1480 ms	9024 KB	Output is correct
18	Correct	1337 ms	8276 KB	Output is correct
19	Correct	947 ms	16960 KB	Output is correct
20	Correct	2131 ms	10688 KB	Output is correct
21	Correct	456 ms	5716 KB	Output is correct
22	Correct	3080 ms	14500 KB	Output is correct
23	Correct	1882 ms	18904 KB	Output is correct
24	Correct	1725 ms	15192 KB	Output is correct
25	Correct	3409 ms	19824 KB	Output is correct
26	Correct	2548 ms	20456 KB	Output is correct
27	Correct	2971 ms	19680 KB	Output is correct
28	Correct	774 ms	36280 KB	Output is correct
29	Correct	1377 ms	62608 KB	Output is correct
30	Correct	1902 ms	27528 KB	Output is correct
31	Correct	1380 ms	21684 KB	Output is correct
32	Correct	499 ms	10344 KB	Output is correct
33	Correct	679 ms	10836 KB	Output is correct
34	Correct	1633 ms	48784 KB	Output is correct
35	Correct	1662 ms	32760 KB	Output is correct
36	Correct	3257 ms	60848 KB	Output is correct
37	Correct	2491 ms	54764 KB	Output is correct
38	Correct	2755 ms	54412 KB	Output is correct
39	Correct	2215 ms	39924 KB	Output is correct
40	Correct	0 ms	344 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 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	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	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	891 ms	11636 KB	Output is correct
13	Correct	338 ms	11344 KB	Output is correct
14	Correct	1252 ms	8568 KB	Output is correct
15	Correct	1515 ms	8488 KB	Output is correct
16	Correct	994 ms	7396 KB	Output is correct
17	Correct	1476 ms	9008 KB	Output is correct
18	Correct	1336 ms	8152 KB	Output is correct
19	Correct	943 ms	16692 KB	Output is correct
20	Correct	2126 ms	10832 KB	Output is correct
21	Correct	456 ms	5716 KB	Output is correct
22	Correct	3041 ms	14336 KB	Output is correct
23	Correct	1864 ms	18688 KB	Output is correct
24	Correct	1732 ms	15252 KB	Output is correct
25	Correct	3400 ms	19264 KB	Output is correct
26	Correct	2559 ms	20156 KB	Output is correct
27	Correct	2949 ms	19964 KB	Output is correct
28	Correct	775 ms	36132 KB	Output is correct
29	Correct	1378 ms	62800 KB	Output is correct
30	Correct	1935 ms	27308 KB	Output is correct
31	Correct	1394 ms	21840 KB	Output is correct
32	Correct	503 ms	10320 KB	Output is correct
33	Correct	677 ms	10576 KB	Output is correct
34	Correct	1656 ms	48680 KB	Output is correct
35	Correct	1693 ms	32700 KB	Output is correct
36	Correct	3259 ms	60796 KB	Output is correct
37	Correct	2533 ms	55068 KB	Output is correct
38	Correct	2780 ms	54628 KB	Output is correct
39	Correct	1090 ms	73088 KB	Output is correct
40	Correct	2162 ms	134736 KB	Output is correct
41	Correct	2827 ms	53148 KB	Output is correct
42	Correct	3233 ms	42332 KB	Output is correct
43	Correct	2618 ms	108500 KB	Output is correct
44	Correct	706 ms	10516 KB	Output is correct
45	Correct	2196 ms	39876 KB	Output is correct
46	Correct	4332 ms	130868 KB	Output is correct
47	Correct	4249 ms	109168 KB	Output is correct
48	Correct	4411 ms	126868 KB	Output is correct
49	Correct	1 ms	348 KB	Output is correct