Submission #1194666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194666		aykhn	Mosaic (IOI24_mosaic)	C++20	100 / 100	270 ms	53000 KiB

mosaic

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

using namespace std;

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> X1, vector<int> X2, vector<int> Y1, vector<int> Y2) 
{
  while (X.size() < 10) X.push_back(0);
  while (Y.size() < 10) Y.push_back(0);
  long long N = X.size();
  vector<vector<long long>> mat(N);
  for (int i = 0; i < N; i++) 
  {
    if (i > 2) mat[i].resize(3);
    else mat[i].resize(N);
  }
  for (int i = 0; i < N; i++) mat[0][i] = X[i], mat[i][0] = Y[i];
  auto pre = mat;
  for (int i = 1; i < N; i++)
  {
    for (int j = 1; j < mat[i].size(); j++) mat[i][j] = !(mat[i - 1][j] | mat[i][j - 1]);
  }
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < mat[i].size(); j++)
    {
      pre[i][j] = (i ? pre[i - 1][j] : 0LL) + (j ? pre[i][j - 1] : 0LL) + mat[i][j] - (i && j ? pre[i - 1][j - 1] : 0LL);
    }
  }
  vector<long long> A(N - 2), B(N - 2);
  for (int i = 2; i < N; i++) A[i - 2] = mat[2][i], B[i - 2] = mat[i][2];
  auto pA = A, pB = B, cA = A, cB = B;
  for (int i = 0; i < pA.size(); i++) pA[i] = (i ? pA[i - 1] : 0LL) + A[i] * i;
  for (int i = 0; i < pB.size(); i++) pB[i] = (i ? pB[i - 1] : 0LL) + B[i] * i;
  for (int i = 0; i < cA.size(); i++) cA[i] = (i ? cA[i - 1] : 0LL) + A[i];
  for (int i = 0; i < cB.size(); i++) cB[i] = (i ? cB[i - 1] : 0LL) + B[i];
  auto sumsmall = [&](int x, int y)
  {
    if (min(x, y) < 0) return 0LL;
    return pre[min(1, x)][y] + pre[x][min(1, y)] - pre[min(1, x)][min(1, y)];
  };
  auto sumdiag = [&](int x, int y)
  {
    if (min(x, y) < 2) return 0LL;
    x -= 2, y -= 2;
    long long cnt = min(y + 1, x + 1);
    long long row = (cA[y] - (y - cnt >= 0 ? cA[y - cnt] : 0)) * (y + 1) - (pA[y] - (y - cnt >= 0 ? pA[y - cnt] : 0)) + (y - cnt >= 0 ? cA[y - cnt] : 0LL) * (x + 1);
    long long col = (cB[x] - (x - cnt >= 0 ? cB[x - cnt] : 0)) * (x + 1) - (pB[x] - (x - cnt >= 0 ? pB[x - cnt] : 0)) + (x - cnt >= 0 ? cB[x - cnt] : 0LL) * (y + 1);
    return row + col - cnt * A[0];
  };
  auto sum = [&](int x, int y)
  {
    return sumsmall(x, y) + sumdiag(x, y);
  };
  auto query = [&](int x1, int y1, int x2, int y2)
  {
    return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
  };
  vector<long long> res;
  for (int i = 0; i < X1.size(); i++)
  {
    res.push_back(query(X1[i], Y1[i], X2[i], Y2[i]));
  }
  return res;
}

• 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