Submission #1275464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275464		baodat	Mosaic (IOI24_mosaic)	C++20	12 / 100	1118 ms	2162688 KiB

mosaic

#include <bits/stdc++.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 = (int)X.size();
    int q = (int)T.size();

    // a: grid of colors (0/1), 0-based indexing
    vector<vector<int>> a(n, vector<int>(n, 0));

    // Initialize first row and first column from X and Y
    for (int j = 0; j < n; ++j) a[0][j] = X[j];
    for (int i = 0; i < n; ++i) a[i][0] = Y[i];

    // Fill rest of the grid per rule
    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;
        }
    }

    // Build 1-based prefix sums: pref[i][j] = sum over a[0..i-1][0..j-1]
    vector<vector<long long>> pref(n + 1, vector<long long>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + a[i-1][j-1];
        }
    }

    // Answer queries
    vector<long long> C(q);
    for (int k = 0; k < q; ++k) {
        int t = T[k], b = B[k], l = L[k], r = R[k];
        // Convert to 1-based for prefix rectangle [t..b] x [l..r]
        int i1 = t + 1, i2 = b + 1, j1 = l + 1, j2 = r + 1;
        long long ans = pref[i2][j2] - pref[t][j2] - pref[i2][l] + pref[t][l];
        C[k] = ans;
    }

    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 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