Submission #1236562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236562		fv3	Mosaic (IOI24_mosaic)	C++20	100 / 100	115 ms	44976 KiB

mosaic

#include "mosaic.h"

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

#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif

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();

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

        int q = int(T.size());
        vector<ll> res(q);
        for (int qq = 0; qq < q; qq++) {
            int l = L[qq], r = R[qq], t = T[qq], b = B[qq];

            int sum = 0;
            for (int i = l; i <= r; i++) {
                for (int j = t; j <= b; j++) {
                    sum += grid[j][i];
                }
            }

            res[qq] = sum;
        }

        return res;
    }

    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] = 1;
        }

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

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

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

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

    for (int qq = 0; qq < q; qq++) {
        int l = L[qq], r = R[qq], t = T[qq], b = B[qq];
        if (min(r, b) < 3) {
            if (r < 3) {
                for (int i = l; i <= r; i++) {
                    C[qq] += ps_y[b+1][i] - ps_y[t][i];
                }
            } else {
                for (int i = t; i <= b; i++) {
                    C[qq] += ps_x[i][r+1] - ps_x[i][l];
                }
            }
            continue;
        }

        if (l < 3) {
            for (int i = l; i < 3; i++) {
                C[qq] += ps_y[b+1][i] - ps_y[t][i];
            }
            l = 3;
        }
        if (t < 3) {
            for (int i = t; i < 3; i++) {
                C[qq] += ps_x[i][r+1] - ps_x[i][l];
            }
            t = 3;
        }

        auto Solve = [&](int row, int col) -> ll {
            int mn = min(row, col);
            int mx = max(row, col);

            int diag_l = n - row - 1;

            int diag_ml = diag_l + mn;
            int diag_mr = diag_ml + (mx - mn);

            int diag_r = col + n - 1;

            ll res = 0;
            res += 1ll * (mn + 1) * (diag_ps[diag_mr + 1] - diag_ps[diag_ml]); 
            res += incr_diag_ps[diag_ml] - 1ll * diag_ps[diag_ml] * diag_l;

            res += 1ll * (diag_r + 2) * (diag_ps[diag_r + 1] - diag_ps[diag_mr + 1]);
            res -= incr_diag_ps[diag_r + 1] - incr_diag_ps[diag_mr + 1];

            return res;
        };

        C[qq] += Solve(b, r) - Solve(b, l-1) - Solve(t-1, r) + Solve(t-1, l-1);
    }

    return C;
}

• 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