Submission #1242975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242975		ericl23302	Mosaic (IOI24_mosaic)	C++20	22 / 100	1047 ms	2162688 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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) {
    int Q = (int)T.size();
    std::vector<long long> C(Q, 0);
    
    int n = X.size();
    if (n == 1) return vector<ll>(Q, X[0]);

    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; ++i) grid[0][i] = X[i], grid[i][0] = Y[i];
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i) grid[i][j] += grid[i - 1][j];
            if (j) grid[i][j] += grid[i][j - 1];
            if (i && j) grid[i][j] -= grid[i - 1][j - 1];
        }
    }

    for (int i = 0; i < Q; ++i) {
        ll res = grid[B[i]][R[i]];
        if (T[i]) res -= grid[T[i] - 1][R[i]];
        if (L[i]) res -= grid[B[i]][L[i] - 1];
        if (T[i] && L[i]) res += grid[T[i] - 1][L[i] - 1];
        C[i] = res;
    }

    return C;
}

• 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