Submission #1177591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177591		madamadam3	Mosaic (IOI24_mosaic)	C++20	22 / 100	993 ms	2162688 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi = vector<int>; 
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

int N, Q;
vvi grid;
vvl prefix;

void output_grid() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << grid[i][j] << " ";
    }

    cout << "\n";
  }
}

void colour_tile(int colour, int x, int y) {
  if (grid[x][y] != -1) return;
  grid[x][y] = colour;

  // down left (-1 +1) and up right (+1 -1)
  if (x > 0 && y < N - 1) {
    int ocol = grid[x-1][y+1];
    int ncol = (colour == 0 && ocol == 0) ? 1 : 0;
    if (ocol != -1) colour_tile(ncol, x, y + 1);
  }

  if (x < N - 1 && y > 0) {
    int ocol = grid[x+1][y-1];
    int ncol = (colour == 0 && ocol == 0) ? 1 : 0;
    if (ocol != -1) colour_tile(ncol, x + 1, y);
  }
}

vl mosaic(vi X, vi Y, vi T, vi B, vi L, vi R) {
  Q = (int) T.size();
  N = (int) X.size();

  grid.assign(N, vi(N, -1));
  prefix.assign(N + 1, vl(N + 1, 0LL));

  bool all_white = true;
  for (int i = 0; i < N; i++) {
    colour_tile(X[i], 0, i);
    colour_tile(Y[i], i, 0);

    all_white = all_white && X[i] == 0 && Y[i] == 0;
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      prefix[i+1][j+1] = prefix[i+1][j] + (ll) grid[i][j];
    }
    for (int j = 0; j < N; j++) {
      prefix[i+1][j+1] += prefix[i][j+1];
    }
  }

  // output_grid();

  vl C(Q, 0);
  for (int qn = 0; qn < Q; qn++) {
    int Lx = T[qn], Rx = B[qn], Ly = L[qn], Ry = R[qn];
    ll tl = 0;

    if (all_white) {
      if (Lx == 0) Lx++;
      if (Ly == 0) Ly++;
      if (Lx > Rx || Ly > Ry) continue;

      ll width = Rx - Lx + 1, height = Ry - Ly + 1;
      if (width % 2 == 0) {
        tl = (width / 2) * height;
      } else if (height % 2 == 0) {
        tl = (height / 2) * width;
      } else {
        ll pL = height / 2, bL = height / 2;
        if (Lx % 2 == Ly % 2) pL++;
        else bL++;
        
        tl = (width / 2 + 1) * pL + (width / 2) * bL;
      }
      C[qn] = tl;
      continue;
    }

    tl += prefix[Rx+1][Ry+1];
    tl += prefix[Lx][Ly];
    tl -= prefix[Lx][Ry+1];
    tl -= prefix[Rx+1][Ly];

    C[qn] = tl;
  }

  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