Submission #1278581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278581		avighna	Mosaic (IOI24_mosaic)	C++20	53 / 100	121 ms	54616 KiB

mosaic

#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>

using int64 = long long;

std::vector<int64> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
  const int n = X.size();
  std::vector mp_x(6, std::vector<bool>(n + 6));
  std::vector mp_y(n + 6, std::vector<bool>(6));
  auto set = [&](int x, int y, int v) {
    if (x <= 5) mp_x[x][y] = v;
    if (y <= 5) mp_y[x][y] = v;
    return v;
  };
  auto get = [&](int x, int y) {
    return x <= 5 ? mp_x[x][y] : mp_y[x][y];
  };

  for (int i = 0; i < n; ++i) {
    set(0, i, X[i]), set(i, 0, Y[i]);
  }

  int min = std::min(-4, 2 - n), max = std::max(4, n - 2);
  std::vector<int> marked(std::max(9, 2 * n - 3));
  for (int i = 1; i <= 5; ++i) {
    for (int j = 1; j < n; ++j) {
      marked[i - j - min] = set(i, j, !get(i - 1, j) && !get(i, j - 1));
      marked[j - i - min] = set(j, i, !get(j - 1, i) && !get(j, i - 1));
    }
  }

  auto get_pt = [&](int x, int y) -> int {
    return (x <= 5 or y <= 5) ? get(x, y) : marked[x - y - min];
  };

  std::vector prefxs(6, std::vector<int>(n)), prefys(6, std::vector<int>(n));
  for (int i = 0; i <= 5; ++i) {
    for (int j = 0; j < n; ++j) {
      prefxs[i][j] = get_pt(i, j);
      prefys[i][j] = get_pt(j, i);
    }
    std::partial_sum(prefxs[i].begin(), prefxs[i].end(), prefxs[i].begin());
    std::partial_sum(prefys[i].begin(), prefys[i].end(), prefys[i].begin());
  }

  auto prefx = [&](int x, int y1, int y2) {
    return prefxs[x][y2] - (y1 == 0 ? 0 : prefxs[x][y1 - 1]);
  };
  auto prefy = [&](int y, int x1, int x2) {
    return prefys[y][x2] - (x1 == 0 ? 0 : prefys[y][x1 - 1]);
  };

  struct adv {
    std::vector<int> marked;
    std::vector<int64> pref, prefa;
    int n;

    adv(std::vector<int> marked) : n(marked.size()), marked(marked), pref(marked.size()), prefa(marked.size()) {
      for (int64 i = 0; i < marked.size(); ++i) {
        prefa[i] = (i + 1) * marked[i];
      }
      std::partial_sum(prefa.begin(), prefa.end(), prefa.begin());
      std::partial_sum(marked.begin(), marked.end(), pref.begin());
    }

    int64 querys(int l, int len) {
      return pref[l + len - 1] - pref[l - 1];
    }
    int64 query(int l, int len) {
      int r = l + len - 1;
      return prefa[r] - prefa[l - 1] - l * (pref[r] - pref[l - 1]);
    }
    int64 queryr(int l, int len) {
      return query(n + len - l - 2, len);
    }
  };
  adv l(marked);
  std::reverse(marked.begin(), marked.end());
  adv r(marked);

  std::vector<int64> ans(T.size());
  for (int i = 0; i < T.size(); ++i) {
    int x1 = T[i], y1 = L[i], x2 = B[i], y2 = R[i];
    while (x1 <= x2 and x1 <= 5) {
      ans[i] += prefx(x1++, y1, y2);
    }
    if (x1 > x2) {
      continue;
    }
    while (y1 <= y2 and y1 <= 5) {
      ans[i] += prefy(y1++, x1, x2);
    }
    if (y1 > y2) {
      continue;
    }
    int steps = x2 - x1 + 1;
    int len = y2 - y1 + 1;
    int mid = std::min(steps, len);
    int gap = std::abs(steps - len);
    int beg = x1 - y2 - min;
    ans[i] += l.query(beg, mid - 1) + mid * l.querys(beg + mid - 1, gap + 1) + r.queryr(beg + gap + 1, mid - 1);
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22