Submission #1143220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143220		ag_1204	Mosaic (IOI24_mosaic)	C++20	100 / 100	925 ms	86564 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back

vi mosaic(vector<signed> X,vector<signed> Y,vector<signed> T,vector<signed> B,vector<signed> L,vector<signed> R) {
  int n=size(X),q=size(T);
  vi C(q);
  vvi v(max(n,(int)3),vi(3,0)); //this vector contains the values of only the first three layers of the binary grid
  if(n>=3){
    for(int i=0;i<3;i++)v[i].resize(n,0);
  } //the first three rows each contain n elements which belong to the first three layers so we have to extend the vector for these rows
  for(int i=0;i<n;i++) v[0][i]=X[i];
  for(int i=0;i<n;i++) v[i][0]=Y[i];
  //initialise the values in the first layer
  for(int i=1;i<n;i++){
    if(v[0][i]==1 || v[1][i-1]==1) v[1][i]=0;
    else v[1][i]=1;
    if(v[1][i]==1 || v[2][i-1]==1) v[2][i]=0;
    else v[2][i]=1;
    //then we fill in the next two rows by following using the previous row
  }
  for(int i=1;i<n;i++){
    if(v[i][0]==1 || v[i-1][1]==1) v[i][1]=0;
    else v[i][1]=1;
    if(v[i][1]==1 || v[i-1][2]==1) v[i][2]=0;
    else v[i][2]=1;
    //then we fill in the next two columns by following using the previous column
  }
  vvi pref(6,vi(n+1,0));
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      pref[j][i+1]=pref[j][i]+v[j][i];
      //row sums
      pref[3+j][i+1]=pref[3+j][i]+v[i][j];
      //column sums
    }
  }
  map<int,int>pref1,pref2;
  //prefix sums of the first two layers
  if(n>=3){
    for(int i=0;i<n;i++){
      pref1[i]=0;
      pref1[-i]=0;
      pref2[i]=0;
      pref2[-i]=0;
    }
    for(int i=n-1;i>=2;i--){
      pref1[2-i]=pref1[1-i]+v[i][2];
    }
    for(int i=3;i<n;i++){
      pref1[i-2]=pref1[i-3]+v[2][i];
    }
    pref2[-(n-3)]=pref1[-(n-3)];
    for(int i=-(n-3);i<=(n-3);i++){
      pref2[i]=pref2[i-1]+pref1[i];
    }
  }
  for(int i=0;i<q;i++){
    C[i]=0;
    int x1=T[i],x2=B[i],y1=L[i],y2=R[i];
    while(x1<2){
      if(x1>x2) break;
      C[i]+=(pref[x1][y2+1]-pref[x1][y1]);
      x1++;
    }
    //we keep incrementing row-wise as we go along the layers till we reach layer 2 (as we precompute the answers for layers 0 and 1 so we only need to consider the subgrid that lies in layers 2 and above)
    if(x1>x2) continue;
    while(y1<2){
      if(y1>y2)break;
      C[i]+=(pref[3+y1][x2+1]-pref[3+y1][x1]);
      y1++;
    }
    //again incremementing till we're in layer 2, this time column-wise
    if(y1>y2) continue;
    int d1=x2-x1+1,d2=y2-y1+1;
    int num=y2-x1;
    C[i]+=pref2[num]-pref2[num-d1]-pref2[num-d2]+pref2[num-d1-d2];
    //then we look at how the subgrid/rectangle maps to layer 2 - the number of occurences of each element of layer 2 in the subrectangle - and we compute what this gives based off of the precomputed values of the prefix sums
  }
	return C;
}

• 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