Submission #1221357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221357		im2xtreme	Mosaic (IOI24_mosaic)	C++20	22 / 100	1014 ms	2162688 KiB

mosaic

#include <iostream>
#include <vector>
#include "mosaic.h"

using namespace std;

vector<long long> mosaic(
    vector<int> X, vector<int> Y,
    vector<int> T, vector<int> B,
    vector<int> L, vector<int> R) {

    int N = X.size(), Q = T.size();
    vector<vector<int>> A(N, vector<int>(N));
    vector<vector<long long>> S(N + 1, vector<long long>(N + 1));

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

    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            A[i][j] = (A[i-1][j] == 0 && A[i][j-1] == 0) ? 1 : 0;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            S[i+1][j+1] = A[i][j] + S[i][j+1] + S[i+1][j] - S[i][j];

    vector<long long> res(Q);
    for (int k = 0; k < Q; k++) {
        int t = T[k], b = B[k], l = L[k], r = R[k];
        res[k] = S[b+1][r+1] - S[t][r+1] - S[b+1][l] + S[t][l];
    }

    return res;
}

• 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