Submission #1189659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189659		Clan328	Mosaic (IOI24_mosaic)	C++20	70 / 100	102 ms	36408 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

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();
  std::vector<long long> C(Q, 0);
  int N = (int)X.size();

  if (N <= 3) {
    vvi mat(N, vi(N));
    mat[0] = X;
    for (int i = 0; i < N; i++) mat[i][0] = Y[i];

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
        }
    }

    for (int i = 0; i < Q; i++) {
        for (int j = T[i]; j <= B[i]; j++) {
            for (int k = L[i]; k <= R[i]; k++) {
                C[i] += mat[j][k];
            }
        }
    }

    return C;
  }

    // vvi mat(N, vi(N));
    // mat[0] = X;
    // for (int i = 0; i < N; i++) mat[i][0] = Y[i];

    // for (int i = 1; i < N; i++) {
    //     for (int j = 1; j < N; j++) {
    //         if (j >= 3 && i > 2) break;
    //         mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
    //     }
    // }

    // for (int i = 3; i < N; i++) {
    //     for (int j = 3; j < N; j++) {
    //         int d = min(i-3+1, j-3+1);
    //         mat[i][j] = mat[i-d][j-d];
    //     }
    // }

    // for (int i = 0; i < Q; i++) {
    //     for (int j = T[i]; j <= B[i]; j++) {
    //         for (int k = L[i]; k <= R[i]; k++) {
    //             C[i] += mat[j][k];
    //         }
    //     }
    // }

    // return C;

  // N > 3
  vvi mat(N);
  for (int i = 0; i < 3; i++) mat[i] = vi(N);
  for (int i = 3; i < N; i++) mat[i] = vi(3);

  mat[0] = X;
  for (int i = 0; i < N; i++) mat[i][0] = Y[i];

  for (int i = 1; i < N; i++) {
    for (int j = 1; j < mat[i].size(); j++) {
        mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
    }
  }

  vvi sumCol(3, vi(N)), sumRow(3, vi(N));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < N; j++) {
        sumCol[i][j] = (j > 0? sumCol[i][j-1] : 0) + mat[j][i];
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < N; j++) {
        sumRow[i][j] = (j > 0? sumRow[i][j-1] : 0) + mat[i][j];
    }
  }

  vi arr(2*N-5);
  int offset = (N-1)-2;
  for (int i = N-1; i >= 2; i--) arr[2-i+offset] = mat[2][i];
  for (int i = 2; i < N; i++) arr[i-2+offset] = mat[i][2];

    // for (auto x : arr) cout << x << " ";
    //     cout << endl;

  vi sumArr(2*N-5), incrArr(2*N-5), decrArr(2*N-5);
  for (int i = 0; i < arr.size(); i++) {
    sumArr[i] = (i > 0? sumArr[i-1] : 0) + arr[i];
    incrArr[i] = (i > 0? incrArr[i-1] : 0) + i*arr[i];
    decrArr[i] = (i > 0? decrArr[i-1] : 0) + (2*N-5-i-1)*arr[i];
  }

  for (int i = 0; i < Q; i++) {
    while (L[i] <= R[i] && L[i] < 3) {
        C[i] += sumCol[L[i]][B[i]]-(T[i] > 0? sumCol[L[i]][T[i]-1] : 0);
        L[i]++;
    }
    if (L[i] > R[i]) continue;
    while (T[i] <= B[i] && T[i] < 3) {
        C[i] += sumRow[T[i]][R[i]]-(L[i] > 0? sumRow[T[i]][L[i]-1] : 0);
        T[i]++;
    }
    if (T[i] > B[i]) continue;
    
    // for (int j = T[i]; j <= B[i]; j++) {
    //     for (int k = L[i]; k <= R[i]; k++) {
    //         int d = min(j-3+1, k-3+1);
    //         C[i] += mat[j-d][k-d];
    //     }
    // }

    int incrR = T[i]-R[i]+offset;
    int incrL = min(B[i]-R[i]+offset, T[i]-L[i]+offset)-1;

    int decrR = max(B[i]-R[i]+offset, T[i]-L[i]+offset)+1;
    int decrL = B[i]-L[i]+offset;

    C[i] += min(B[i]-T[i]+1, R[i]-L[i]+1)*(sumArr[decrR-1]-sumArr[incrL]);
    C[i] += (incrArr[incrL]-(incrR > 0 ? incrArr[incrR-1] : 0))+(1-incrR)*(sumArr[incrL]-(incrR > 0 ? sumArr[incrR-1] : 0));

    C[i] += (decrArr[decrL]-(decrR > 0 ? decrArr[decrR-1] : 0))+(1-(2*N-5-decrL-1))*(sumArr[decrL]-(decrR > 0 ? sumArr[decrR-1] : 0));
    // cout << decrR << " " << decrL << endl;
    // cout << (decrArr[decrL]-(decrR > 0 ? decrArr[decrR-1] : 0))+(1-(2*N-5-decrL-1))*(sumArr[decrL]-(decrR > 0 ? sumArr[decrR-1] : 0)) << endl;
  }

  return C;
}

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