Submission #1216321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216321		shmax	Mosaic (IOI24_mosaic)	C++20	100 / 100	218 ms	55776 KiB

mosaic

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

using namespace std;
using i32 = int32_t;
#define int long long

template<typename T>
using vec = vector<T>;

template<typename it>
struct PrefixSum {
    using T = typename remove_reference<decltype(*declval<it>())>::type;
    vector<T> pref;

    PrefixSum() = default;

    PrefixSum(it first, it last) {
        pref = vector<T>(distance(first, last) + 1);
        for (int i = 0; i < pref.size(); i++)
            pref[i] = (i == 0 ? 0 : pref[i - 1]) + *(first + i);


    }

    T operator()(int l, int r) {
        assert(l >= 0 && r < pref.size());
        assert(l <= r);
        if (l > r)
            return 0;
        if (l == 0)
            return pref[r];
        return pref[r] - pref[l - 1];
    }
};


std::vector<int> mosaic(std::vector<i32> X, std::vector<i32> Y,
                        std::vector<i32> T, std::vector<i32> B,
                        std::vector<i32> L, std::vector<i32> R) {


    int n = (int) X.size();
    if (n < 3) {
        vec<vec<bool>> a(n, vec<bool>(n, false));
        for (int i = 0; i < n; i++) {
            a[0][i] = X[i];
            a[i][0] = Y[i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                a[i][j] = !(a[i - 1][j] | a[i][j - 1]);
            }
        }

        vec<int> ans;
        int q = T.size();
        while (q--) {
            int sum = 0;
            for (int i = T[q]; i <= B[q]; i++) {
                for (int j = L[q]; j <= R[q]; j++) {
                    if (a[i][j]) sum++;
                }
            }
            ans.push_back(sum);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    {
//        vec<vec<bool>> a(n, vec<bool>(n, false));
//        for (int i = 0; i < n; i++) {
//            a[0][i] = X[i];
//            a[i][0] = Y[i];
//        }
//        for (int i = 1; i < n; i++) {
//            for (int j = 1; j < n; j++) {
//                a[i][j] = !(a[i - 1][j] | a[i][j - 1]);
//            }
//        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                cout << a[i][j] << " ";
//            }
//            cout << endl;
//        }
    }
    vec<vec<bool>> top(3, vec<bool>(n, false));
    for (int i = 0; i < n; i++) {
        top[0][i] = X[i];
    }
    top[1][0] = Y[1];
    top[2][0] = Y[2];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < 3; j++) {
            top[j][i] = !(top[j - 1][i] || top[j][i - 1]);
        }
    }

    vec<vec<bool>> left(n, vec<bool>(3, false));
    for (int i = 0; i < n; i++) {
        left[i][0] = Y[i];
    }
    left[0][1] = X[1];
    left[0][2] = X[2];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < 3; j++) {
            left[i][j] = !(left[i - 1][j] || left[i][j - 1]);
        }
    }
    vec<vec<int>> topPref(3, vec<int>(n, 0));
    vec<vec<int>> leftPref(n, vec<int>(3, 0));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            topPref[i][j] = top[i][j];
            if (i)
                topPref[i][j] += topPref[i - 1][j];
            if (j)
                topPref[i][j] += topPref[i][j - 1];
            if (i && j)
                topPref[i][j] -= topPref[i - 1][j - 1];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            leftPref[i][j] = left[i][j];
            if (i)
                leftPref[i][j] += leftPref[i - 1][j];
            if (j)
                leftPref[i][j] += leftPref[i][j - 1];
            if (i && j)
                leftPref[i][j] -= leftPref[i - 1][j - 1];
        }
    }
    vec<int> top_a(n - 2, 0);
    for (int i = 2; i < n; i++) {
        top_a[i - 2] = top[2][i];
    }
    vec<int> top_a_id = top_a;
    for (int i = (int) top_a.size() - 1; i >= 0; i--) {
        top_a_id[i] *= (int) (top_a.size() - i);
    }
    vec<int> left_a(n - 3, 0);
    for (int i = 3; i < n; i++) {
        left_a[i - 3] = left[i][2];
    }
    vec<int> left_a_id = left_a;
    for (int i = (int) left_a.size() - 1; i >= 0; i--) {
        left_a_id[i] *= (int) (left_a.size() - i);
    }

    PrefixSum top_a_ps(top_a.begin(), top_a.end());
    PrefixSum left_a_ps(left_a.begin(), left_a.end());
    PrefixSum top_a_id_ps(top_a_id.begin(), top_a_id.end());
    PrefixSum left_a_id_ps(left_a_id.begin(), left_a_id.end());
    auto get = [&](int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0LL;
        }
        if (i <= 2) {
            return topPref[i][j];
        }
        if (j <= 2) {
            return leftPref[i][j];
        }
        int ans = topPref[1][j] + leftPref[i][1] - topPref[1][1];
        {
            int start = 0;
            if (j > i) {
                ans += top_a_ps(0, j - i - 1) * (i - 1);
                start = j - i;
            }
            ans += top_a_id_ps(start, j - 2) - top_a_ps(start, j - 2) * ((int) top_a.size() - (j - 2) - 1);
        }
        {
            int start = 0;
            if (i - 1 > j) {
                ans += left_a_ps(0, i - j - 2) * (j - 1);
                start = i - j - 1;
            }
            ans += left_a_id_ps(start, i - 3) - left_a_ps(start, i - 3) * ((int) left_a.size() - (i - 3) - 1);
        }
        return ans;
    };
    int q = (int) T.size();
    vec<int> ans;
    while (q--) {
        auto [t, b, l, r] = tuple(T[q], B[q], L[q], R[q]);
        ans.push_back(get(b, r) - get(t - 1, r) - get(b, l - 1) + get(t - 1, l - 1));
    }
    reverse(ans.begin(), ans.end());
    return ans;

}

• 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