Mosaic

mosaic
English (ISC)
Mosaic
Salma plans to colour a clay mosaic on a wall. The mosaic is an N × N grid, made of N initially
uncoloured 1 × 1 square tiles. The rows of the mosaic are numbered from 0 to N −1 from top to
bottom, and the columns are numbered from 0 to N −1 from left to right. The tile in row i and
column j (0 ≤i < N, 0 ≤j < N) is denoted by (i,j). Each tile must be coloured either white
(denoted by 0) or black (denoted by 1).
To colour the mosaic, Salma first picks two arrays X and Y of length N, each consisting of values 0
and 1, such that X[0] = Y [0]. She colours the tiles of the topmost row (row 0) according to array
X, such that the colour of tile (0,j) is X[j] (0 ≤j < N). She also colours the tiles of the leftmost
column (column 0) according to array Y , such that the colour of tile (i,0) is Y [i] (0 ≤i < N).
Then she repeats the following steps until all tiles are coloured:
She finds any uncoloured tile (i,j) such that its up neighbor (tile (i −1,j)) and left neighbor
(tile (i,j −1)) are both already coloured.
Then, she colours tile (i,j) black if both of these neighbors are white; otherwise, she colours
tile (i,j) white.
It can be shown that the final colours of the tiles do not depend on the order in which Salma is
colouring them.
Yasmin is very curious about the colours of the tiles in the mosaic. She asks Salma Q questions,
numbered from 0 to Q −1. In question k (0 ≤k < Q), Yasmin specifies a subrectangle of the
mosaic by its:
Topmost row T[k] and bottommost row B[k] (0 ≤T[k] ≤B[k] < N),
Leftmost column L[k] and rightmost column R[k] (0 ≤L[k] ≤R[k] < N).
The answer to the question is the number of black tiles in this subrectangle. Specifically, Salma
should find how many tiles (i,j) exist, such that T[k] ≤i ≤B[k], L[k] ≤j ≤R[k], and the colour
of tile (i,j) is black.
Write a program that answers Yasmin's questions.
Implementation Details
You should implement the following procedure.
2
mosaic (1 of 3)

std::vector mosaic(
std::vector X, std::vector Y,
std::vector T, std::vector B,
std::vector L, std::vector R)‎
X, Y : arrays of length N describing the colours of the tiles in the topmost row and the
leftmost column, respectively.
T, B, L, R: arrays of length Q describing the questions asked by Yasmin.
The procedure should return an array C of length Q, such that C[k] provides the answer to
question k (0 ≤k < Q).
This procedure is called exactly once for each test case.
Constraints
1 ≤N ≤200 000
1 ≤Q ≤200 000
X[i] ∈{0,1} and Y [i] ∈{0,1} for each i such that 0 ≤i < N
X[0] = Y [0]
0 ≤T[k] ≤B[k] < N and 0 ≤L[k] ≤R[k] < N for each k such that 0 ≤k < Q
Subtasks
Subtask
Score
Additional Constraints
1
5
N ≤2;Q ≤10
2
7
N ≤200;Q ≤200
3
7
T[k] = B[k] = 0 (for each k such that 0 ≤k < Q)
4
10
N ≤5000
5
8
X[i] = Y [i] = 0 (for each i such that 0 ≤i < N)
6
22
T[k] = B[k] and L[k] = R[k] (for each k such that 0 ≤k < Q)
7
19
T[k] = B[k] (for each k such that 0 ≤k < Q)
8
22
No additional constraints.
Example
Consider the following call.
mosaic([1, 0, 1, 0], [1, 1, 0, 1], [0, 2], [3, 3], [0, 0], [3, 2])‎
mosaic (2 of 3)

This example is illustrated in the pictures below. The left picture shows the colours of the tiles in
the mosaic. The middle and right pictures show the subrectangles Yasmin asked about in the first
and second question, respectively.
The answers to the questions (that is, the numbers of ones in the shaded rectangles) are 7 and 3,
respectively. Hence, the procedure should return [7,3].
Sample Grader
Input format:
N
X[0] X[1] ... X[N-1]
Y[0] Y[1] ... Y[N-1]
Q
T[0] B[0] L[0] R[0]
T[1] B[1] L[1] R[1]
...
T[Q-1] B[Q-1] L[Q-1] R[Q-1]‎
Output format:
C[0]
C[1]
...
C[S-1]‎
Here, S is the length of the array C returned by ‎mosaic‎.
mosaic (3 of 3)

Input / Output on this judge

This is the IOI function-implementation task mosaic adapted to standard input / output. Instead of implementing the function, read its arguments from standard input and print the returned value(s) to standard output, exactly as the official grader below does (its internal anti-cheat checks have been removed). You may also simply submit the grader together with your own implementation of the function.

Function signature (mosaic.h):

#include <vector>

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);

Reference I/O driver (official grader, sanitized):

#include "mosaic.h"
#include <cassert>
#include <cstdio>
#include <vector>

int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &X[i]));
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Y[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> T(Q), B(Q), L(Q), R(Q);
  for (int k = 0; k < Q; k++)
    assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
  fclose(stdin);

  std::vector<long long> C = mosaic(X, Y, T, B, L, R);

  int S = (int)C.size();
  for (int k = 0; k < S; k++)
    printf("%lld\n", C[k]);
  fclose(stdout);

  return 0;
}

rip 작성

출처 IOI 2024