Submission #1177594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177594		madamadam3	Mosaic (IOI24_mosaic)	C++20	30 / 100	1069 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();

    bool should_prefix = false;
    bool all_white = true;
    for (int i = 0; i < N; i++) {
      all_white = all_white && X[i] == 0 && Y[i] == 0;
    }

    should_prefix = !all_white;

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

      for (int i = 0; i < N; i++) {
        colour_tile(X[i], 0, i);
        colour_tile(Y[i], 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;
        }
      } else if (should_prefix) {
        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: 8 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22