제출 #1223028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223028		LucaIlie	모자이크 (IOI24_mosaic)	C++20	22 / 100	269 ms	204096 KiB

mosaic

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

using namespace std;

const int MAX_N = 2e5;
const int MAX_N2 = 5001;
int mat[MAX_N2][MAX_N2], sp[MAX_N2][MAX_N2];
int diag[2 * MAX_N2 + 5];

vector<long long> mosaic(vector<int> X, vector<int> Y,
                              vector<int> T, vector<int> B,
                              vector<int> L, vector<int> R) {

  int n = X.size();
  int q = (int)T.size();
  vector<long long> ans(q);

  for (int c = 1; c <= n; c++)
      mat[1][c] = X[c - 1];
  for (int l = 1; l <= n; l++)
      mat[l][1] = Y[l - 1];


  for (int l = 2; l <= n; l++) {
      for (int c = 2; c <= n; c++)
          mat[l][c] = !(mat[l][c - 1] | mat[l - 1][c]);
  }

  // for (int l = 1; l <= n; l++) {
  //     for (int c = 1; c <= n; c++)
  //         printf("%d ", mat[l][c]);
  //     printf("\n");
  // }
  
  for (int d = 0; d <= 2 * n + 1; d++)
      diag[d] = -1;

  for (int l = 4; l <= n; l++) {
      for (int c = 4; c <= n; c++) {
          int d = l - c + n;
          if (diag[d] == -1)
              diag[d] = mat[l][c];
          assert(diag[d] == mat[l][c]);
      }
  }

  for (int l = 1; l <= n; l++) {
      for (int c = 1; c <= n; c++)
          sp[l][c] = mat[l][c] + sp[l][c - 1] + sp[l - 1][c] - sp[l - 1][c - 1];
  }

  for (int i = 0; i < q; i++) {
      int l1 = T[i] + 1, l2 = B[i] + 1, c1 = L[i] + 1, c2 = R[i] + 1;
      ans[i] = sp[l2][c2] - sp[l1 - 1][c2] - sp[l2][c1 - 1] + sp[l1 - 1][c1 - 1];
  }

  return ans;
}

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