Submission #1244405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244405		MarwenElarbi	Mosaic (IOI24_mosaic)	C++20	7 / 100	98 ms	20412 KiB

mosaic

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

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 n = X.size();
  int q = T.size();
  bool x[4][n];
  bool y[n][4];
  for (int i = 0; i < n; ++i)
  {
    x[0][i]=X[i];
    y[i][0]=Y[i];
  }
  for (int i = 0; i < 4; ++i)
  {
    x[i][0]=Y[i];
    y[0][i]=X[i];
  }
  for (int i = 1; i < 4; ++i)
  {
    for (int j = 1; j < n; ++j)
    {
      if(x[i-1][j]+x[i][j-1]==0) x[i][j]=1;
      else x[i][j]=0;
    }
  }
  for (int i = 1; i < n; ++i)
  {
    for (int j = 1; j < 4; ++j)
    {
      if(y[i-1][j]+y[i][j-1]==0) y[i][j]=1;
      else y[i][j]=0;
    }
  }
  int prefx[4][n];
  int prefy[n][4];
  for (int i = 0; i < 4; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      prefx[i][j]=x[i][j];
      if(j) prefx[i][j]+=prefx[i][j-1];
    }
  }
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < 4; ++j)
    {
      prefy[i][j]=y[i][j];
      if(j) prefy[i][j]+=prefy[i][j-1];
    }
  }
  vector<long long> ans;
  int pre[n];
  for (int i = 0; i < n; ++i)
  {
    pre[i]=y[i][3];
    if(i) pre[i]+=pre[i-1];
  }
  for (int k = 0; k < q; ++k)
  {
    int t=T[k];
    int i=L[k];
    int j=R[k];
    if(t<=3) ans.push_back(prefx[t][j]-(i ? prefx[t][i-1] : 0));
    else if (j<=3) ans.push_back(prefy[t][j]-(i ? prefy[t][i-1] : 0));
    else{
      int cur = 0;
      int up = t - 3; 
      if(i<=3){
        cur+=prefy[t][3]-(i ? prefy[t][i-1] : 0);
        i=4;
      }
      if(j-up>=3&&i-up>=3) cur+=prefx[3][j-up]-prefx[3][i-up-1];
      else if(j-up>=3){
        cur+=prefx[3][j-up]-prefx[3][3];
        cur+=pre[t-(i-3)]-pre[2];
      }
      else{
        cur-=pre[t-(j-3)];
        cur+=pre[t-(i-3)];
      }
      ans.push_back(cur);
    }
  }
  return ans;
}

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