Submission #1278460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278460		avighna	Mosaic (IOI24_mosaic)	C++20	12 / 100	1104 ms	173400 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::map<std::pair<int, int>, int> mp;
  for (int i = 0; i < n; ++i) {
    mp[{0, i}] = X[i];
    mp[{i, 0}] = Y[i];
  }

  for (int i = 1; i <= 100; ++i) {
    for (int j = 1; j < n; ++j) {
      mp[{i, j}] = !mp[{i - 1, j}] && !mp[{i, j - 1}];
    }
  }
  for (int j = 1; j <= 100; ++j) {
    for (int i = 1; i < n; ++i) {
      mp[{i, j}] = !mp[{i - 1, j}] && !mp[{i, j - 1}];
    }
  }

  int min = 0, max = 0;

  for (auto &[pt, y] : mp) {
    if (pt.first != 0 and pt.second != 0 and y != 0) {
      int v = pt.first - pt.second;
      min = std::min(min, v);
      max = std::max(max, v);
    }
  }

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

  for (auto &[pt, y] : mp) {
    if (pt.first != 0 and pt.second != 0 and y != 0) {
      int v = pt.first - pt.second;
      marked[v - min] = true;
    }
  }

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

  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) {
      for (int v = y1; v <= y2; ++v) {
        cur += get_pt(u, v);
      }
    }
    ans.push_back(cur);
  }
  return ans;
}

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