제출 #926402

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

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ll = long long;

struct Tree;
struct Tree2;
long long gcd2(long long X, long long Y);

map<int,int> treeV;
vector<Tree> tree(10'000'000); int nextfree = 1;
vector<Tree2> tree2(1'000'000); int nextfree2 = 1;

int R, C;

struct Tree {
  int left, right; ll val;
  Tree() : left(0), right(0), val(0) {}
  void update(int v, int xl, int xr, ll delta) {
    if (v < xl || v > xr) return;
    if (xl == xr) {
      val = delta;
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = nextfree++;
        tree[left].update(v, xl, xm, delta);
      } else {
        if (!right) right = nextfree++;
        tree[right].update(v, xm+1, xr, delta);
      }
      val = 0;
      if (left) val = gcd2(val, tree[left].val);
      if (right) val = gcd2(val, tree[right].val);
    }
  }
  ll query(int l, int r, int xl, int xr) {
    if (l > r) return 0;
    if (l == xl && r == xr) {
      return val;
    } else {
      int xm = (xl + xr) / 2;
      ll ans = 0;
      if (left) 
        ans = gcd2(ans, tree[left].query(l, min(r, xm), xl, xm));
      if (right) 
        ans = gcd2(ans, tree[right].query(max(l, xm+1), r, xm+1, xr));
      return ans;
    }
  }
};

struct Tree2 {
  int left, right, val;
  Tree2() : left(0), right(0), val(0) {}
  void update(int v, int w, int xl, int xr, ll delta) {
    if (v < xl || v > xr) return;
    ll delta2 = tree[treeV[w]].query(xl, xr, 0, R-1);
    if (!val) val = nextfree++;
    tree[val].update(w, 0, C-1, delta2);
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = nextfree2++;
        tree2[left].update(v, w, xl, xm, delta);
      } else {
        if (!right) right = nextfree2++;
        tree2[right].update(v, w, xm+1, xr, delta);
      }
    }
  }
  ll query(int l, int r, int l2, int r2, int xl, int xr) {
    if (l > r) return 0;
    if (l == xl && r == xr) {
      if (!val) return 0;
      return tree[val].query(l2, r2, 0, C-1);
    } else {
      int xm = (xl + xr) / 2;
      ll ans = 0;
      if (left) 
        ans = gcd2(ans, tree2[left].query(l, min(r, xm), l2, r2, xl, xm));
      if (right)
        ans = gcd2(ans, tree2[right].query(max(l, xm+1), r, l2, r2, xm+1, xr));
      return ans;
    }
  }
};

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;
}

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

void update(int P, int Q, long long K) {
  if (treeV.count(Q) == 0) treeV[Q] = nextfree++;
  tree[treeV[Q]].update(P, 0, R-1, K);
  tree2[0].update(P, Q, 0, R-1, K);
}

long long calculate(int P, int Q, int U, int V) {
  return tree2[0].query(P, U, Q, V, 0, R-1);
}

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