제출 #956078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956078		abczz	게임 (IOI13_game)	C++14	63 / 100	1304 ms	256000 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long

using namespace std;

ll gcd(ll a, ll b) {
  if (!b) return a;
  else if (!a) return b;
  else return gcd(b%a, a);
}
struct SegTree{
  struct Node{
    ll val = 0;
    ll chl = -1;
    ll chr = -1;
    ll chm = -1;
  };
  ll cnt = 0;
  vector <Node> st;
  void get(ll &id) {
    if (id != -1) return;
    st.push_back({0, -1, -1, -1});
    id = cnt++;
  }
  void updateC(ll &id, ll idl, ll idr, ll l, ll r, ll y, ll w) {
    get(id);
    if (l == r) {
      if (idl == -1 && idr == -1) st[id].val = w;
      else st[id].val = gcd((idl != -1 ? st[idl].val : 0), (idr != -1 ? st[idr].val : 0));
      return;
    }
    ll mid = (l+r)/2;
    if (y <= mid) {
      ll tmp = st[id].chl;
      updateC(tmp, (idl != -1 ? st[idl].chl : -1), (idr != -1 ? st[idr].chl : -1), l, mid, y, w);
      st[id].chl = tmp;
    }
    else {
      ll tmp = st[id].chr;
      updateC(tmp, (idl != -1 ? st[idl].chr : -1), (idr != -1 ? st[idr].chr : -1), mid+1, r, y, w);
      st[id].chr = tmp;
    }
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  void updateR(ll &id, ll l, ll r, ll x, ll y, ll w) {
    get(id);
    if (l == r) {
      ll tmp = st[id].chm;
      updateC(tmp, -1, -1, 0, (ll)1e9-1, y, w);
      st[id].chm = tmp;
      st[id].val = st[st[id].chm].val;
      return;
    }
    ll mid = (l+r)/2;
    if (x <= mid) {
      ll tmp = st[id].chl;
      updateR(tmp, l, mid, x, y, w);
      st[id].chl = tmp;
    }
    else {
      ll tmp = st[id].chr;
      updateR(tmp, mid+1, r, x, y, w);
      st[id].chr = tmp;
    }
    ll tmp = st[id].chm;
    updateC(tmp, (st[id].chl != -1 ? st[st[id].chl].chm : -1), (st[id].chr != -1 ? st[st[id].chr].chm : -1), 0, (ll)1e9-1, y, w);
    st[id].chm = tmp;
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  ll queryC(ll id, ll l, ll r, ll ql, ll qr) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) {
      return st[id].val;
    }
    ll mid = (l+r)/2;
    return gcd(queryC(st[id].chl, l, mid, ql, qr), queryC(st[id].chr, mid+1, r, ql, qr));
  }
  ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll qx, ll qy) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return queryC(st[id].chm, 0, (ll)1e9-1, qx, qy);
    ll mid = (l+r)/2;
    return gcd(queryR(st[id].chl, l, mid, ql, qr, qx, qy), queryR(st[id].chr, mid+1, r, ql, qr, qx, qy));
  }
}ST;

void init(int R, int C) {
  ll rt = -1;
  ST.get(rt);
}

void update(int P, int Q, long long K) {
  ll rt = 0;
  ST.updateR(rt, 0, (ll)1e9-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  ll rt = 0;
  return ST.queryR(rt, 0, (ll)1e9-1, P, U, Q, V);
}

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