Submission #967334

#	Time	Username	Problem	Language	Result	Execution time	Memory
967334		obokaman	Game (IOI13_game)	C++17	100 / 100	4171 ms	65652 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20