Submission #1205197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205197		HappyCapybara	Mosaic (IOI24_mosaic)	C++20	100 / 100	109 ms	38768 KiB

mosaic

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

#define ll long long

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
  int N = X.size(), Q = T.size();
  if (N < 4){
    vector<vector<int>> bruh(N, vector<int>(N));
    bruh[0] = X;
    for (int i=1; i<N; i++) bruh[i][0] = Y[i];
    for (int i=1; i<N; i++){
      for (int j=1; j<N; j++) bruh[i][j] = 1-(bruh[i-1][j] | bruh[i][j-1]);
    }
    vector<ll> res(Q, 0);
    for (int k=0; k<Q; k++){
      for (int i=T[k]; i<=B[k]; i++){
        for (int j=L[k]; j<=R[k]; j++) res[k] += bruh[i][j];
      }
    }
    return res;
  }
  vector<vector<int>> h(3, vector<int>(N)), v(3, vector<int>(N));
  h[0] = X;
  v[0] = Y;
  for (int i=1; i<3; i++){
    h[i][0] = Y[i];
    v[i][0] = X[i];
  }
  for (int i=1; i<3; i++){
    for (int j=1; j<N; j++){
      h[i][j] = 1-(h[i-1][j] | h[i][j-1]);
      v[i][j] = 1-(v[i-1][j] | v[i][j-1]);
    }
  }
  vector<ll> z;
  for (int i=N-1; i>=2; i--) z.push_back(v[2][i]);
  for (int i=3; i<N; i++) z.push_back(h[2][i]);
  vector<vector<ll>> psh(3, vector<ll>(N+1, 0)), psv(3, vector<ll>(N+1, 0));
  for (int i=0; i<3; i++){
    for (int j=0; j<N; j++){
      psh[i][j+1] = psh[i][j]+h[i][j];
      psv[i][j+1] = psv[i][j]+v[i][j];
    }
  }
  int s = 2*N-5;
  vector<ll> psz(s+1, 0), zx(s+1), xz(s+1);
  for (int i=0; i<s; i++){
    psz[i+1] = psz[i]+z[i];
    zx[i+1] = zx[i]+z[i]*(ll)(i+1);
    xz[i+1] = xz[i]+z[i]*(ll)(s-i);
  }
  vector<ll> res(Q, 0);
  for (int i=0; i<Q; i++){
    for (int j=T[i]; j<=min(B[i], 2); j++) res[i] += psh[j][R[i]+1]-psh[j][L[i]];
    if (B[i] >= 3){
      for (int j=L[i]; j<=min(R[i], 2); j++) res[i] += psv[j][B[i]+1]-psv[j][max(T[i], 3)];
    }
    if (B[i] < 3 || R[i] < 3) continue;
    int a = max(3, L[i])-B[i]+(N-3), b = max(3, L[i])-max(3, T[i])+(N-3), c = R[i]-B[i]+(N-3), d = R[i]-max(3, T[i])+(N-3);
    if (b > c) swap(b, c);
    //cout << a << " " << b << " " << c << " " << d << endl;
    res[i] += zx[b]-zx[a]-(psz[b]-psz[a])*(ll)a + xz[d+1]-xz[c+1]-(psz[d+1]-psz[c+1])*(ll)(s-1-d) + (psz[c+1]-psz[b])*(ll)(b-a+1);
  }
  return res;
}

• 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