제출 #1223045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223045		LucaIlie	모자이크 (IOI24_mosaic)	C++20	0 / 100	83 ms	23880 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];
int matL[4][MAX_N], matC[MAX_N + 1][4];
int spL[4][MAX_N], spC[MAX_N + 1][4];
int diag[2 * MAX_N + 5];
int n;

long long getImportantSumRectangle(int l1, int c1, int l2, int c2) {
    if (l1 > l2 || c1 > c2)
        return 0;

    int d1 = l1 - c2 + n, d2 = l2 - c1 + n;
    int maxx = min(l2 - l1, c2 - c1);

    long long ans = 0;
    for (int d = d1; d < d1 + maxx && d <= d2; d++) 
        ans += diag[d] * (d - d1 + 1);

    for (int d = d1 + maxx; d <= d2 - maxx; d++)
        ans += diag[d] * maxx;
        
    for (int d = d2; d > d2 - maxx && d >= d1; d--)
        ans += diag[d] * (d2 - d + 1);

    // printf("%d %d\n", d1, d2);
    // for (int d = d1; d <= d2; d++)
    //     printf("%d\n", diag[d]);
    // printf("imp %d %d %d %d -> %lld\n", l1, c1, l2, c2, ans);

    return ans;
}

int getSumL(int l1, int c1, int l2, int c2) {
    return spL[l2][c2] - spL[l2][c1 - 1] - spL[l1 - 1][c2] + spL[l1 - 1][c1 - 1];
}

int getSumC(int l1, int c1, int l2, int c2) {
    return spC[l2][c2] - spC[l2][c1 - 1] - spC[l1 - 1][c2] + spC[l1 - 1][c1 - 1];
}

long long getSumRectangle(int l1, int c1, int l2, int c2) {
    if (l1 < 3)
        return matL[l2][c2];
    if (c1 < 3)
        return matC[l2][c2];
    long long ans = getImportantSumRectangle(max(l1, 3), max(c1, 3), l2, c2);
    return ans;
    if (l1 < 3)
        ans += getSumL(l1, c1, min(l2, 2), c2);
    if (c1 < 3)
        ans += getSumC(l1, c1, l2, min(c2, 2));
    if (l1 < 3 && c1 < 3)
        ans -= getSumL(l1, c1, min(l2, 2), min(c2, 2));
    return ans;
}

vector<long long> mosaic(vector<int> X, vector<int> Y,
                              vector<int> T, vector<int> B,
                              vector<int> L, vector<int> R) {
  n = X.size();
  int q = (int)T.size();
  vector<long long> ans(q);

  for (int c = 1; c <= n; c++)
      matL[1][c] = X[c - 1];
  for (int c = 1; c <= 3; c++)
      matC[1][c] = X[c - 1];

  for (int l = 1; l <= n; l++)
      matC[l][1] = Y[l - 1];
  for (int l = 1; l <= 3; l++)
      matL[l][1] = Y[l - 1];

  for (int d = 0; d <= 2 * n + 1; d++)
      diag[d] = -1;

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

  for (int l = 1; l <= 3; l++) {
      for (int c = 1; c <= n; c++)
          spL[l][c] = spL[l - 1][c] + spL[l][c - 1] - spL[l - 1][c - 1] + matL[l][c];
  }
  for (int l = 1; l <= n; l++) {
      for (int c = 1; c <= 3; c++)
          spC[l][c] = spC[l - 1][c] + spC[l][c - 1] - spC[l - 1][c - 1] + matC[l][c];
  }

  for (int c = 3; c <= n; c++) 
      diag[3 - c + n] = matL[3][c];
  for (int l = 3; l <= n; l++) 
      diag[l - 3 + n] = matC[l][3];

  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] = getSumRectangle(l1, c1, l2, c2);
  }

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 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