Submission #926415

#	Time	Username	Problem	Language	Result	Execution time	Memory
926415		myst6	게임 (IOI13_game)	C++14	63 / 100	13102 ms	52552 KiB

game

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

using namespace std;
using ll = long long;

long long gcd2(long long X, long long Y);

const int N = 20'000'000;
const int K = 3;
int lptr[N], rptr[N]; ll val[N];
int nextfree = 1;

int R, C;

void update1(int idx, int v, int xl, int xr, ll delta) {
  if (v < xl || v > xr) return;
  if (xl == xr) {
    val[idx] = delta;
  } else {
    int xm = (xl + xr) / 2;
    if (v <= xm) {
      if (!lptr[idx]) lptr[idx] = nextfree++;
      update1(lptr[idx], v, xl, xm, delta);
    } else {
      if (!rptr[idx]) rptr[idx] = nextfree++;
      update1(rptr[idx], v, xm+1, xr, delta);
    }
    val[idx] = 0;
    if (lptr[idx]) val[idx] = gcd2(val[idx], val[lptr[idx]]);
    if (rptr[idx]) val[idx] = gcd2(val[idx], val[rptr[idx]]);
  }
}

ll query1(int idx, int l, int r, int xl, int xr) {
  if (l > r) return 0;
  if (l == xl && r == xr) {
    return val[idx];
  } else {
    int xm = (xl + xr) / 2;
    ll ans = 0;
    if (lptr[idx]) ans = gcd2(ans, query1(lptr[idx], l, min(r, xm), xl, xm));
    if (rptr[idx]) ans = gcd2(ans, query1(rptr[idx], max(l, xm+1), r, xm+1, xr));
    return ans;
  }
}

ll query2(int idx, int l, int r, int l2, int r2, int xl, int xr) {
  if (l > r) return 0;
  if (l == xl && r == xr && val[idx] != -1) {
    if (!val[idx]) return 0;
    return query1(val[idx], l2, r2, 1, C);
  } else {
    int xm = (xl + xr) / 2;
    ll ans = 0;
    if (lptr[idx]) ans = gcd2(ans, query2(lptr[idx], l, min(r, xm), l2, r2, xl, xm));
    if (rptr[idx]) ans = gcd2(ans, query2(rptr[idx], max(l, xm+1), r, l2, r2, xm+1, xr));
    return ans;
  }
}

void update2(int idx, int v, int w, int xl, int xr, ll delta) {
  if (v < xl || v > xr) return;
  if (xl != xr) {
    int xm = (xl + xr) / 2;
    if (v <= xm) {
      if (!lptr[idx]) lptr[idx] = nextfree++;
      update2(lptr[idx], v, w, xl, xm, delta);
    } else {
      if (!rptr[idx]) rptr[idx] = nextfree++;
      update2(rptr[idx], v, w, xm+1, xr, delta);
    }
  }
  if (!val[idx]) {
    // sacrifice runtime for memory
    if (xl != xr && rand() % K != 0) val[idx] = -1;
    else val[idx] = nextfree++;
  }
  if (val[idx] != -1) {
    ll delta2 = delta;
    int xm = (xl + xr) / 2;
    if (lptr[idx]) delta2 = gcd2(delta2, query2(lptr[idx], xl, xm, w, w, xl, xm));
    if (rptr[idx]) delta2 = gcd2(delta2, query2(rptr[idx], xm+1, xr, w, w, xm+1, xr));
    if (!val[idx]) val[idx] = nextfree++;
    update1(val[idx], w, 1, C, delta2);
  }
}

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) {
  update2(0, P+1, Q+1, 1, R, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query2(0, P+1, U+1, Q+1, V+1, 1, R);
}

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