제출 #1163720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163720		iah	게임 (IOI13_game)	C++20	63 / 100	1152 ms	321536 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int row, col;

struct Seg{
  struct Node {
    int l, r;
    ll val;
    Node *lc, *rc;

    Node () {
      l = 0;
      r = 0;
      val = 0;
      lc = nullptr;
      rc = nullptr;
    }

    Node (int _l, int _r) {
      l = _l;
      r = _r;
      val = 0;
      lc = nullptr;
      rc = nullptr;
    }

    void update(int pos, ll x) {
      if (l == r) {
        val = x;
        return;
      }

      int mid = l + r >> 1;

      if (pos <= mid) {
        if (!lc) {
          lc = new Node(l, mid);
        }

        lc -> update(pos, x);
      }
      else {
        if (!rc) {
          rc = new Node(mid + 1, r);
        }

        rc -> update(pos, x);
      }

      val = __gcd(lc ? lc -> val : 0, rc ? rc -> val : 0);
    }

    ll get(int u, int v) {
      if (u <= l && r <= v) {
        return val;
      }

      int mid = l + r >> 1;

      if (v < mid + 1) {
        return lc ? lc -> get(u, v) : 0;
      }

      if (u > mid) {
        return rc ? rc -> get(u, v) : 0;
      }

      return __gcd(lc ? lc -> get(u, v) : 0, rc ? rc -> get(u, v) : 0);
    }
  };

  int l, r;
  Seg *lc, *rc;
  Node *root;

  Seg() {
    l = 0;
    r = 0;
    lc = nullptr;
    rc = nullptr;
    root = nullptr;
  }

  Seg(int _l, int _r) {
    l = _l;
    r = _r;
    lc = nullptr;
    rc = nullptr;
    root = new Node(1, col);
  }

  void update(int u, int v, ll x) {
    if (l == r) {
      root -> update(v, x);
      return;
    }

    int mid = l + r >> 1;

    if (mid >= u) {
      if (!lc) {
        lc = new Seg(l, mid);
      }

      lc -> update(u, v, x);
    }
    else {
      if (!rc) {
        rc = new Seg(mid + 1, r);
      }

      rc -> update(u, v, x);
    }

    ll j = __gcd(lc ? lc -> root -> get(v, v) : 0, rc ? rc -> root -> get(v, v) : 0);
//    cerr << l << " " << r << " " << u << " " << v << " " << j << "\n";

    root -> update(v, j);
  }

  ll get(int p, int q, int u, int v) {
    if (p <= l && r <= u) {
//      cerr << l << " " << r << " " << root -> get(q, v) << "\n";
      return root -> get(q, v);
    }

    int mid = l + r >> 1;

    if (mid + 1 > u) {
      return lc ? lc -> get(p, q, u, v) : 0;
    }

    if (mid < p) {
      return rc ? rc -> get(p, q, u, v) : 0;
    }

    return __gcd(lc ? lc -> get(p, q, u, v) : 0, rc ? rc -> get(p, q, u, v) : 0);
  }
};

Seg *root = nullptr;

void init(int R, int C) {
  row = R;
  col = C;

//  cerr << "init " << R << " " << C << "\n";

  root = new Seg(1, row);
}

void update(int P, int Q, long long K) {
  P ++;
  Q ++;
//  cerr << "update " << P << " " << Q << " " << K << "\n";
  root -> update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  P ++;
  Q ++;
  U ++;
  V ++;
//  cerr << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
  return root -> get(P, Q, U, V);
}

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