Submission #1236444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236444		fv3	Mosaic (IOI24_mosaic)	C++20	48 / 100	97 ms	29360 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

    const int n = X.size();
    vector<vector<int>> grid(n, vector<int>(3));

    swap(grid[0], X);
    for (int i = 0; i < n; i++) {
        grid[i][0] = Y[i];
    }

    for (int i = 1; i < min(3, n); i++) {
        grid[i].resize(n);
        for (int j = 1; j < n; j++) {
            grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
        }
    }

    for (int i = 3; i < n; i++) {
        for (int j = 1; j < 3; j++) {
            grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
        }
    }

    vector<int> diag(2*n-1);
    for (int i = 2; i < n; i++) {
        if (grid[2][i]) {
            diag[i-2 + n] = 1;
        }

        if (grid[i][2]) {
            diag[2-i + n] = 1;
        }
    }
    vector<int> diag_ps(2*n);
    for (int i = 0; i < 2*n-1; i++) {
        diag_ps[i+1] = diag_ps[i] + diag[i];
    }

    vector<vector<int>> ps(3, vector<int>(n+1));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            ps[i][j+1] = ps[i][j] + grid[i][j];
        }
    }

    int q = (int)T.size();
    vector<ll> C(q, 0);

    for (int qq = 0; qq < q; qq++) {
        assert(T[qq] == B[qq]);

        if (T[qq] < 3) {
            C[qq] = ps[T[qq]][R[qq]+1] - ps[T[qq]][L[qq]];
        } else {
            if (R[qq] < 3) {
                int res = 0;
                for (int i = L[qq]; i <= R[qq]; i++) {
                    res += grid[T[qq]][i];
                }
                C[qq] = res;
            } else {
                int res = 0;
                for (int i = L[qq]; i < 3; i++) {
                    res += grid[T[qq]][i];
                }
                L[qq] = max(L[qq], 3);

                res += diag_ps[R[qq] - T[qq] + n + 1] - diag_ps[L[qq] - T[qq] + n];
                C[qq] = res;
            }
        }
    }

    return C;
}

//#include "grader.cpp"

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