Submission #1307976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307976		regulardude6	모자이크 (IOI24_mosaic)	C++20	100 / 100	89 ms	27072 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();
    vector<long long> result(Q);

    // Prefix sums for the first row and first column
    vector<long long> prefX(N + 1, 0), prefY(N + 1, 0);
    for (int i = 0; i < N; i++) {
        prefX[i + 1] = prefX[i] + X[i];
        prefY[i + 1] = prefY[i] + Y[i];
    }

    // Layer 1 sequences (row and column parts)
    int n1 = N >= 1 ? N - 1 : 0;
    vector<int> rowSeq1(n1, 0);
    vector<long long> prefixRow1(n1 + 1, 0);
    if (n1 > 0) {
        rowSeq1[0] = (X[1] == 0 && Y[1] == 0) ? 1 : 0;
        for (int k = 1; k < n1; k++) {
            rowSeq1[k] = (rowSeq1[k - 1] == 0 && X[k + 1] == 0) ? 1 : 0;
        }
        for (int i = 0; i < n1; i++) prefixRow1[i + 1] = prefixRow1[i] + rowSeq1[i];
    }

    int n_c1 = N >= 2 ? N - 2 : 0;
    vector<int> colSeq1(n_c1, 0);
    vector<long long> prefixCol1(n_c1 + 1, 0);
    if (n_c1 > 0) {
        colSeq1[0] = (rowSeq1[0] == 0 && Y[2] == 0) ? 1 : 0;
        for (int k = 1; k < n_c1; k++) {
            colSeq1[k] = (colSeq1[k - 1] == 0 && Y[k + 2] == 0) ? 1 : 0;
        }
        for (int i = 0; i < n_c1; i++) prefixCol1[i + 1] = prefixCol1[i] + colSeq1[i];
    }

    // Layer 2 sequences (row and column parts)
    int n2 = N >= 2 ? N - 2 : 0;
    vector<int> rowSeq2(n2, 0);
    vector<long long> prefixRow2(n2 + 1, 0), sumPrefixRow2(n2 + 2, 0);
    if (n2 > 0) {
        rowSeq2[0] = (rowSeq1[1] == 0 && colSeq1[0] == 0) ? 1 : 0;
        for (int k = 1; k < n2; k++) {
            rowSeq2[k] = (rowSeq1[k + 1] == 0 && rowSeq2[k - 1] == 0) ? 1 : 0;
        }
        for (int i = 0; i < n2; i++) {
            prefixRow2[i + 1] = prefixRow2[i] + rowSeq2[i];
        }
        for (int i = 0; i <= n2; i++) {
            sumPrefixRow2[i + 1] = sumPrefixRow2[i] + prefixRow2[i];
        }
    }

    int n3 = N >= 3 ? N - 3 : 0;
    vector<int> colSeq2(n3, 0);
    vector<long long> prefixCol2(n3 + 1, 0), sumPrefixCol2(n3 + 2, 0);
    if (n3 > 0) {
        colSeq2[0] = (rowSeq2[0] == 0 && colSeq1[1] == 0) ? 1 : 0;
        for (int k = 1; k < n3; k++) {
            colSeq2[k] = (colSeq2[k - 1] == 0 && colSeq1[k + 1] == 0) ? 1 : 0;
        }
        for (int i = 0; i < n3; i++) {
            prefixCol2[i + 1] = prefixCol2[i] + colSeq2[i];
        }
        for (int i = 0; i <= n3; i++) {
            sumPrefixCol2[i + 1] = sumPrefixCol2[i] + prefixCol2[i];
        }
    }

    for (int qi = 0; qi < Q; qi++) {
        int t = T[qi], b = B[qi], lq = L[qi], rq = R[qi];
        long long total = 0;

        // Layer 0: row and column 0
        if (t <= 0 && 0 <= b) {
            int sj = max(lq, 0), ej = rq;
            if (sj <= ej) total += prefX[ej + 1] - prefX[sj];
        }
        if (lq <= 0 && 0 <= rq) {
            int si = max(t, 1), ei = b;
            if (si <= ei) total += prefY[ei + 1] - prefY[si];
        }

        // Layer 1: row 1, col >=1 and col 1, row >=2
        if (n1 > 0 && t <= 1 && 1 <= b && rq >= 1) {
            int ks = max(lq, 1) - 1;
            int ke = min(rq - 1, n1 - 1);
            if (ks <= ke) total += prefixRow1[ke + 1] - prefixRow1[ks];
        }
        if (n_c1 > 0 && lq <= 1 && 1 <= rq && b >= 2) {
            int is_ = max(t, 2);
            int ie = b;
            int ks = is_ - 2;
            int ke = min(ie - 2, n_c1 - 1);
            if (ks <= ke) total += prefixCol1[ke + 1] - prefixCol1[ks];
        }

        // Layers >=2: row parts
        if (n2 > 0 && rq >= 2 && b >= 2) {
            int ls = max(2, t), le = min(b, rq);
            if (ls <= le) {
                int i_start = rq - le + 1;
                int i_end   = rq - ls + 1;
                long long sumEnd = sumPrefixRow2[i_end + 1] - sumPrefixRow2[i_start];

                int leftEnd = min(le, lq);
                long long sumStart = 0;
                if (leftEnd >= ls) {
                    int a = lq - leftEnd;
                    int z = lq - ls;
                    sumStart = sumPrefixRow2[z + 1] - sumPrefixRow2[a];
                }
                total += sumEnd - sumStart;
            }
        }

        // Layers >=2: column parts
        if (n3 > 0 && rq >= 2 && b >= 3) {
            int ls = max(2, lq);
            int le = min(rq, b - 1);
            if (ls <= le) {
                int i_start = b - le;
                int i_end   = b - ls;
                long long sumEnd = sumPrefixCol2[i_end + 1] - sumPrefixCol2[i_start];

                int lowEnd = min(le, t - 1);
                long long sumStart = 0;
                if (lowEnd >= ls) {
                    int a = t - lowEnd - 1;
                    int z = t - ls - 1;
                    if (z >= 0) {
                        int A = max(0, a);
                        sumStart = sumPrefixCol2[z + 1] - sumPrefixCol2[A];
                    }
                }
                total += sumEnd - sumStart;
            }
        }

        result[qi] = total;
    }
    return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 22 / 22