Submission #1177587

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

  for (int i = 0; i < N; i++) {
    colour_tile(X[i], 0, i);
  }

  for (int i = 0; i < 3; i++) {
    colour_tile(Y[i], i, 0);
  }

  for (int i = 0; i < 3; 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];
    }
  }

  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;

    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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22