제출 #1268128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268128		angelolan	게임 (IOI13_game)	C++20	100 / 100	4756 ms	51384 KiB

game

#include <bits/stdc++.h>
#include "game.h"
// Pura Gente del Coach Moy y la Alexbriza

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r) {
	return std::uniform_int_distribution<int>(l, r)(rng);
}

using ll = long long;

ll gcd(ll a, ll b) {
  return !b ? a : gcd(b, a % b);
}

struct TreapNode {
  TreapNode *l = 0, *r = 0;
  int i, j, y;
  ll val, g;
  TreapNode(int i, int j, ll val) : i(i), j(j), y(random(0, 1000000000)), val(val), g(val) {}
  void recalc();
};

ll getGcd(TreapNode* n) { return n ? n->g : 0; }

void TreapNode::recalc() { g = gcd(val, gcd(getGcd(l), getGcd(r))); }

std::pair<TreapNode*, TreapNode*> split(TreapNode* n, int i, int j) {
  if (!n) return {};
  if (n->j > j || (n->j == j && n->i >= i)) {
    auto [L,R] = split(n->l, i, j);
    n->l = R;
    n->recalc();
    return {L, n};
  } else {
    auto [L,R] = split(n->r, i, j);
    n->r = L;
    n->recalc();
    return {n, R};
  }
}

TreapNode* merge(TreapNode* l, TreapNode* r) {
  if (!l) return r;
  if (!r) return l;
  if (l->y > r->y) {
    l->r = merge(l->r, r);
    return l->recalc(), l;
  } else {
    r->l = merge(l, r->l);
    return r->recalc(), r;
  }
}

void setTreap(TreapNode*& n, int i, int j, ll x) {
  auto [L1, R1] = split(n, i, j);
  auto [L2, R2] = split(R1, i + 1, j);
  n = merge(L1, merge(new TreapNode(i, j, x), R2));
}

ll queryTreap(TreapNode* n, int j1, int j2) {
  auto [L1, R1] = split(n, 0, j1);
  auto [L2, R2] = split(R1, 0, j2);
  ll g = getGcd(L2);
  n = merge(L1, merge(L2, R2));
  return g;
}

struct STreeNode {
  TreapNode* treapRoot = 0;
  int l = -1, r = -1;
};

int N, curr = 1;
STreeNode st[500000];

int set(int v, int tl, int tr, int i, int j, ll val) {
  if (tl > i || tr <= i) return v;
  if (v == -1) {
    v = curr++;
  }
  setTreap(st[v].treapRoot, i, j, val);
  if (tl + 1 == tr) return v;
  int tm = (tl + tr) / 2;
  i < tm ? st[v].l = set(st[v].l, tl, tm, i, j, val) : st[v].r = set(st[v].r, tm, tr, i, j, val);
  return v;
}

ll query(int v, int tl, int tr, int i1, int i2, int j1, int j2) {
  if (tr <= i1 || i2 <= tl || v == -1) return 0; 
  if (i1 <= tl && tr <= i2) return queryTreap(st[v].treapRoot, j1, j2);
  int tm = (tl + tr) / 2;
  if (i1 < tm && i2 > tm) {
    return gcd(query(st[v].l, tl, tm, i1, i2, j1, j2), query(st[v].r, tm, tr, i1, i2, j1, j2));
  } else if (i1 < tm) {
    return query(st[v].l, tl, tm, i1, i2, j1, j2);
  }
  return query(st[v].r, tm, tr, i1, i2, j1, j2);
}

void set(int i, int j, ll val) { set(0, 0, N, i, j, val); }
ll query(int i1, int i2, int j1, int j2) { return query(0, 0, N, i1, i2, j1, j2); }

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

void update(int P, int Q, ll K) { set(P, Q, K); }

ll calculate(int P, int Q, int U, int V) { return query(P, U + 1, Q, V + 1); }

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20