Submission #1190992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190992		tyellow	Game (IOI13_game)	C++17	63 / 100	1090 ms	278748 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()


int n, m;

struct SegNode1D {
  ll val = 0;
  SegNode1D *lp = nullptr, *rp = nullptr;
};

struct SegmentTree1D {
  SegNode1D *node;
  void modify(int l, int r, SegNode1D *&p, int q, ll val) {
    if (p == nullptr)
      p = new SegNode1D;
    if (l == r) {
      p->val = val;
      return;
    }
    int mid = l + r >> 1;
    if (q <= mid)
      modify(l, mid, p->lp, q, val);
    else
      modify(mid + 1, r, p->rp, q, val);
    p->val = gcd(p->lp ? p->lp->val : 0, p->rp ? p->rp->val : 0);
  }
  void modify(int q, ll val) { modify(1, m, node, q, val); }

  ll query(int l, int r, SegNode1D *&p, int ql, int qr) {
    if (!p || ql > r || qr < l) return 0;
    if (ql <= l && r <= qr)
      return p->val;
    int mid = l + r >> 1;
    return gcd(p->lp ? query(l, mid, p->lp, ql, qr) : 0, p->rp ? query(mid + 1, r, p->rp, ql, qr) : 0);
  }
  ll query(int ql, int qr) { return query(1, m, node, ql, qr); }
};

struct SegNode2D {
  SegmentTree1D val;
  SegNode2D *lp = nullptr, *rp = nullptr;
};

struct SegmentTree2D {
  SegNode2D *node;
  void modify(int l, int r, SegNode2D *&p, int x, int y, ll val) {
    if (p == nullptr)
      p = new SegNode2D;
    if (l == r) {
      p->val.modify(y, val);
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
      modify(l, mid, p->lp, x, y, val);
    else 
      modify(mid + 1, r, p->rp, x, y, val);
    p->val.modify(y, gcd(p->lp ? p->lp->val.query(y, y) : 0, p->rp ? p->rp->val.query(y, y) : 0));
  }
  void modify(int x, int y, ll val) { modify(1, n, node, x, y, val); }

  ll query(int l, int r, SegNode2D *&p, int U, int D, int L, int R) {
    if (!p || U > r || D < l) return 0;
    if (U <= l && r <= D)
      return p->val.query(L, R);
    int mid = l + r >> 1;
    return gcd(p->lp ? query(l, mid, p->lp, U, D, L, R) : 0, p->rp ? query(mid + 1, r, p->rp, U, D, L, R) : 0);
  }
  ll query(int U, int D, int L, int R) { return query(1, n, node, U, L, D, R); }
} tree;

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

void update(int P, int Q, ll K) {
  tree.modify(++P, ++Q, K);
}

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

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