Submission #1246606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246606		2008	Mosaic (IOI24_mosaic)	C++20	22 / 100	1097 ms	2162688 KiB

mosaic

#include "mosaic.h"
using namespace std;
#include <vector>

std::vector<long long> 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) {
  int Q = (int)T.size();
  int N = (int)X.size();
  int mosaic[N][N];
  int countBLACK[N][N];
  countBLACK[0][0] = X[0];
  for (int i=0; i<N; i++) {
    mosaic[0][i] = X[i];
    mosaic[i][0] = Y[i];
    if (i>0) {
      countBLACK[0][i] = X[i]+countBLACK[0][i-1];
      countBLACK[i][0] = Y[i]+countBLACK[i-1][0];
    }
  }
  for (int i=1; i<N; i++) {
    for (int j=1; j<N; j++) {
      if (mosaic[i-1][j]==0 && mosaic[i][j-1]==0) {
        mosaic[i][j] = 1;
      } else {
        mosaic[i][j] = 0;
      }
      countBLACK[i][j] = countBLACK[i-1][j]+countBLACK[i][j-1]+mosaic[i][j]-countBLACK[i-1][j-1];
    }
  }
  vector<long long> C(Q, 0);
  for (int i=0; i<Q; i++) {
    C[i] = countBLACK[B[i]][R[i]];
    if (T[i] > 0) {
      C[i]-=countBLACK[T[i]-1][R[i]];
    }
    if (L[i] > 0) {
      C[i]-=countBLACK[B[i]][L[i]-1];
    }
    if (T[i] > 0 && L[i] > 0) {
      C[i]+=countBLACK[T[i]-1][L[i]-1];
    }
  }
  return C;
}

• 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