Submission #967333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967333	2024-04-22T02:18:50 Z	obokaman	Game (IOI13_game)	C++17	100 / 100	3975 ms	67752 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 of [P, Q]x[R, S], knowing that t covers [a,b]
ll query(RowNode* 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 <= Q) {
    return gcdRS(thick_row(t), R, S);
  } else {
    ll gcd_x = (P <= t->x && t->x <= Q) ? gcdRS(row(t), R, S) : -1;
    return gcd(gcd_x, gcd(query(t->l, P, Q, R, S, a, t->x-1),
			  query(t->r, P, Q, R, S, t->x+1, b)));
  }
}

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

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) {
    //    cout << "*query t=[" << a << "," << b << ")  P=" << P << " Q=" << Q << endl;
    ll res = gcdRS(t->row, R, S);
    //    cout << "  res = " << res << endl;
    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));
    //    cout << "query t=[" << a << "," << b << ")  P=" << P << " Q=" << Q << endl;
    //    cout << "  res = " << res << endl;
    return res;
  }
}

void print(Node* t) {
  if (t) {
    cout << "[";
    print(t->l);
    cout << " " << t->x << "|" << t->val << "|" << t->gcd << "-" << t->prio << " ";
    print(t->r);
    cout << "]";
  }
}

void print(SSTNode* t, int a, int b) {
  if (t) {
    cout << "a=" << a << " b=" << b << " ";
    print(row(t));
    cout << endl;
    if (a+1 < b) {
      int m = (a+b)/2;
      print(t->l, a, m);
      print(t->r, m, b);
    }
  }
}

RowNode* globalt = nullptr;
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(globalt, P, Q, K);
  set(gn, P, Q, K, 0, Rp2);
  //  print(gn, 0, Rp2);
  //  cout << endl;
}
ll calculate(int P, int Q, int R, int S) {
  //  ll res = query(globalt, P, R, Q, S, 0, globalRows-1);
  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	432 KB	Output is correct
4	Correct	1 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	344 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	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	589 ms	11868 KB	Output is correct
5	Correct	261 ms	11604 KB	Output is correct
6	Correct	925 ms	8976 KB	Output is correct
7	Correct	1066 ms	9152 KB	Output is correct
8	Correct	751 ms	7628 KB	Output is correct
9	Correct	1027 ms	8768 KB	Output is correct
10	Correct	951 ms	8656 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	1 ms	348 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	600 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	440 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	946 ms	13340 KB	Output is correct
13	Correct	1967 ms	7724 KB	Output is correct
14	Correct	304 ms	5552 KB	Output is correct
15	Correct	2147 ms	9088 KB	Output is correct
16	Correct	635 ms	11888 KB	Output is correct
17	Correct	1484 ms	9684 KB	Output is correct
18	Correct	2439 ms	13244 KB	Output is correct
19	Correct	2090 ms	12856 KB	Output is correct
20	Correct	2063 ms	12316 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	432 KB	Output is correct
4	Correct	0 ms	428 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	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	1 ms	348 KB	Output is correct
12	Correct	562 ms	11896 KB	Output is correct
13	Correct	273 ms	11588 KB	Output is correct
14	Correct	955 ms	9292 KB	Output is correct
15	Correct	1101 ms	8920 KB	Output is correct
16	Correct	717 ms	8156 KB	Output is correct
17	Correct	1022 ms	9056 KB	Output is correct
18	Correct	980 ms	8816 KB	Output is correct
19	Correct	910 ms	13440 KB	Output is correct
20	Correct	1945 ms	7812 KB	Output is correct
21	Correct	293 ms	5484 KB	Output is correct
22	Correct	2130 ms	9452 KB	Output is correct
23	Correct	625 ms	11340 KB	Output is correct
24	Correct	1476 ms	9772 KB	Output is correct
25	Correct	2410 ms	12708 KB	Output is correct
26	Correct	2150 ms	13212 KB	Output is correct
27	Correct	2073 ms	12548 KB	Output is correct
28	Correct	740 ms	36340 KB	Output is correct
29	Correct	1362 ms	39104 KB	Output is correct
30	Correct	2515 ms	28380 KB	Output is correct
31	Correct	2236 ms	23744 KB	Output is correct
32	Correct	409 ms	10068 KB	Output is correct
33	Correct	640 ms	10788 KB	Output is correct
34	Correct	1160 ms	33252 KB	Output is correct
35	Correct	1653 ms	24240 KB	Output is correct
36	Correct	2998 ms	36936 KB	Output is correct
37	Correct	2419 ms	37016 KB	Output is correct
38	Correct	2544 ms	36496 KB	Output is correct
39	Correct	2052 ms	30884 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct

Subtask #5

20.0 / 20.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	0 ms	432 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	570 ms	12148 KB	Output is correct
13	Correct	265 ms	11660 KB	Output is correct
14	Correct	925 ms	9348 KB	Output is correct
15	Correct	1056 ms	9140 KB	Output is correct
16	Correct	706 ms	7760 KB	Output is correct
17	Correct	1014 ms	9180 KB	Output is correct
18	Correct	947 ms	8644 KB	Output is correct
19	Correct	903 ms	13792 KB	Output is correct
20	Correct	1956 ms	7892 KB	Output is correct
21	Correct	295 ms	5644 KB	Output is correct
22	Correct	2108 ms	8936 KB	Output is correct
23	Correct	625 ms	11456 KB	Output is correct
24	Correct	1494 ms	9632 KB	Output is correct
25	Correct	2440 ms	12784 KB	Output is correct
26	Correct	2117 ms	13232 KB	Output is correct
27	Correct	2093 ms	12428 KB	Output is correct
28	Correct	753 ms	36184 KB	Output is correct
29	Correct	1399 ms	39248 KB	Output is correct
30	Correct	2536 ms	28528 KB	Output is correct
31	Correct	2194 ms	23596 KB	Output is correct
32	Correct	417 ms	10320 KB	Output is correct
33	Correct	675 ms	10500 KB	Output is correct
34	Correct	1174 ms	32812 KB	Output is correct
35	Correct	1744 ms	23968 KB	Output is correct
36	Correct	3067 ms	36996 KB	Output is correct
37	Correct	2498 ms	37640 KB	Output is correct
38	Correct	2609 ms	36484 KB	Output is correct
39	Correct	1139 ms	65584 KB	Output is correct
40	Correct	2376 ms	67752 KB	Output is correct
41	Correct	3675 ms	52216 KB	Output is correct
42	Correct	3453 ms	41756 KB	Output is correct
43	Correct	1454 ms	62312 KB	Output is correct
44	Correct	578 ms	10660 KB	Output is correct
45	Correct	2067 ms	30848 KB	Output is correct
46	Correct	3975 ms	66564 KB	Output is correct
47	Correct	3913 ms	66824 KB	Output is correct
48	Correct	3913 ms	66160 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct