Submission #1278531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278531		avighna	Mosaic (IOI24_mosaic)	C++20	34 / 100	1096 ms	34976 KiB

mosaic

#include <map>
#include <numeric>
#include <set>
#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;
    }
  };
  auto get = [&](int x, int y) {
    if (x <= 5) {
      return mp_x[x][y];
    }
    return mp_y[x][y];
  };
  for (int i = 0; i < n; ++i) {
    set(0, i, X[i]);
    set(i, 0, Y[i]);
  }

  int min = 0, max = 0;

  for (int i = 1; i <= 5; ++i) {
    for (int j = 1; j < n; ++j) {
      set(i, j, !get(i - 1, j) && !get(i, j - 1));
      int v = i - j;
      min = std::min(min, i - j);
      max = std::max(max, i - j);
    }
  }
  for (int j = 1; j <= 5; ++j) {
    for (int i = 1; i < n; ++i) {
      set(i, j, !get(i - 1, j) && !get(i, j - 1));
      int v = i - j;
      min = std::min(min, i - j);
      max = std::max(max, i - j);
    }
  }

  std::vector<int> marked(max - min + 1);

  for (int i = 1; i <= 5; ++i) {
    for (int j = 1; j < n; ++j) {
      if (!get(i, j)) {
        continue;
      }
      int v = i - j;
      marked[v - min] = true;
    }
  }
  for (int j = 1; j <= 5; ++j) {
    for (int i = 1; i < n; ++i) {
      if (!get(i, j)) {
        continue;
      }
      int v = i - j;
      marked[v - min] = true;
    }
  }

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

  std::vector prefxs(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);
    }
    std::partial_sum(prefxs[i].begin(), prefxs[i].end(), prefxs[i].begin());
  }

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

  std::vector<int> pref(max - min + 1);
  std::accumulate(marked.begin(), marked.end(), pref.begin());

  auto sum = [&](int x, int y1, int y2) {
    int beg = x - y2 - min, end = x - y1 - min;
    return pref[end] - (beg == 0 ? 0 : pref[beg - 1]);
  };

  std::vector<int64> ans;
  for (int i = 0; i < T.size(); ++i) {
    int x1 = T[i], y1 = L[i], x2 = B[i], y2 = R[i];
    int64 cur = 0;
    for (int u = x1; u <= x2; ++u) {
      if (u <= 5) {
        cur += prefx(u, y1, y2);
      } else {
        int y1n = y1, y2n = y2;
        for (int cnt = 0; y1n <= y2 && cnt < 6; ++y1n, ++cnt) {
          cur += get_pt(u, y1n);
        }
        for (int cnt = 0; y1n <= y2n && cnt < 6; --y2n, ++cnt) {
          cur += get_pt(u, y2n);
        }
        if (y1n <= y2n) {
          cur += sum(u, y1n, y2n);
        }
      }
    }
    ans.push_back(cur);
  }
  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: 0 / 19
• Subtask 8: 0 / 22