Submission #1105033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105033		flashmt	Mosaic (IOI24_mosaic)	C++17	100 / 100	193 ms	52668 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long> mosaic(
  vector<int> X, vector<int> Y,
  vector<int> T, vector<int> B,
  vector<int> L, vector<int> R
) {
  int n = size(X);
  vector<vector<int>> a(n);
  a[0] = X;
  for (int i = 1; i < n; i++)
  {
    int len = i < 3 ? n : 3;
    a[i].resize(len);
    a[i][0] = Y[i];
    for (int j = 1; j < len; j++)
      a[i][j] = (a[i - 1][j] | a[i][j - 1]) ^ 1;
  }

  vector<vector<long long>> s(n);
  for (int i = 0; i < n; i++)
  {
    int len = i < 3 ? n : 3;
    s[i].resize(len);
    s[i][0] = a[i][0];
    if (i)
      s[i][0] += s[i - 1][0];
    for (int j = 1; j < len; j++)
    {
      s[i][j] = s[i][j - 1] + a[i][j];
      if (i)
        s[i][j] += s[i - 1][j] - s[i - 1][j - 1];
    }
  }

  vector<long long> sumRow(n), sumCol(n), cntRow(n), cntCol(n);
  for (int i = 2; i < n; i++)
  {
    sumRow[i] = sumRow[i - 1] + (a[2][i] ? i : 0);
    cntRow[i] = cntRow[i - 1] + a[2][i];
    sumCol[i] = sumCol[i - 1] + (a[i][2] ? i : 0);
    cntCol[i] = cntCol[i - 1] + a[i][2];
  }

  auto getColTriangle = [&](int x, int xx)
  {
    return 1LL * xx * (cntCol[xx - 1] - cntCol[x - 2]) - (sumCol[xx - 1] - sumCol[x - 2]);
  };

  auto getRowTriangle = [&](int y, int yy)
  {
    return 1LL * yy * (cntRow[yy - 1] - cntRow[y - 2]) - (sumRow[yy - 1] - sumRow[y - 2]);
  };

  auto get = [&](int x, int y)
  {
    if (x < 0 || y < 0)
      return 0LL;
    if (x < 3 || y < 3)
      return s[x][y];
    long long res = s[2][y] + s[x][2] - s[2][2];
    if (x <= y)
    {
      if (x >= 4)
        res += getColTriangle(4, x);
      res += getRowTriangle(y - (x - 3), y);
      res += (cntRow[y - (x - 1)] - cntRow[1]) * (x - 2);
    }
    else
    {
      if (y >= 4)
        res += getRowTriangle(4, y);
      res += getColTriangle(x - (y - 3), x);
      res += (cntCol[x - (y - 1)] - cntCol[1]) * (y - 2);
    }
    return res;
  };

  int q = size(T);
  vector<long long> ans(q);
  for (int i = 0; i < q; i++)
  {
    ans[i] = get(B[i], R[i]) + get(T[i] - 1, L[i] - 1);
    ans[i] -= get(B[i], L[i] - 1) + get(T[i] - 1, R[i]);
  }
  return ans;
}

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