Submission #1313497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313497		joonwu04	모자이크 (IOI24_mosaic)	C++20	100 / 100	107 ms	41944 KiB

mosaic

#include "mosaic.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <span>
using namespace std;

using ll = long long;

template <typename T>
class Array2D {
    int H = 0, W = 0;
    vector<T> data;

    public:
        Array2D() = default;

        Array2D(int h, int w): H(h), W(w), data(h * w) {}
        Array2D(int h, int w, T val): H(h), W(w), data(h * w, val) {}
        
        T& operator()(int i, int j) {
            assert(0 <= i && i < H  &&  0 <= j && j < W);
            return data[i * W + j];
        }
        const T& operator()(int i, int j) const {
            assert(0 <= i && i < H  &&  0 <= j && j < W);
            return data[i * W + j];
        }

        int height() const { return H; }
        int width() const { return W; }

        vector<T> row(int i) const {
            assert(0 <= i && i < H);

            vector<T> out;
            out.reserve(W);

            for (int j = 0; j < W; ++j) out.push_back(data[i * W + j]);
            
            return out;
        }

        vector<T> col(int j) const {
            assert(0 <= j && j < W);

            vector<T> out;
            out.reserve(H);

            for (int i = 0; i < H; ++i) out.push_back(data[i * W + j]);
            
            return out;
        }

        void print() const {
            for (int i = 0; i < H; ++i) {
                for (int j = 0; j < W; ++j) {
                    cout << (*this)(i, j) << " ";
                }
                cout << endl;
            }
        }

        void print1() const {
            for (int i = 1; i < H; ++i) {
                for (int j = 1; j < W; ++j) {
                    cout << (*this)(i, j) << " ";
                }
                cout << endl;
            }
        }
};

template <typename T, typename S = ll>
class PrefixSum1D {
    vector<S> dp;

    public:
        PrefixSum1D() = default;

        PrefixSum1D(const vector<T>& arr) {   
            build(arr);
        }

        void build(const vector<T>& arr) {
            int n = (int)arr.size();
            dp = vector<S>(n + 1, (S)0);

            for (int i = 1; i <= n; ++i) {
                dp[i] = arr[i-1] + dp[i-1];
            }
        }

        // dp: 1-indexed
        S rangeSumOnDp(int l, int r) const {
            return dp[r] - dp[l-1];
        }

        // arr: 0-indexed
        S rangeSum(int l, int r) const {
            if (l > r) return 0;
            return rangeSumOnDp(l + 1, r + 1);
        }

        // void print() {
        //     print(dp);
        // }
};

template <typename T, typename S = ll>
class PrefixSum2D {
    Array2D<S> dp;

    public:
        PrefixSum2D() = default;

        PrefixSum2D(const Array2D<T>& grid) {   
            build(grid);
        }

        void build(const Array2D<T>& grid) {   
            int h = grid.height(), w = grid.width();
            dp = Array2D<S>(h + 1, w + 1, (S)0);

            for (int i = 1; i <= h; ++i) {
                for (int j = 1; j <= w; ++j) {
                    dp(i, j) = (S)grid(i-1, j-1) + dp(i-1, j) + dp(i, j-1) - dp(i-1, j-1); 
                }
            }
        }

        // dp: 1-indexed
        S rectSumOnDp(int a, int b, int c, int d) const {
            return dp(c, d) - dp(c, b-1) - dp(a-1, d) + dp(a-1, b-1);
        }

        // grid: 0-indexed
        S rectSum(int a, int b, int c, int d) const {
            if (a > c || b > d) return 0;
            return rectSumOnDp(a+1, b+1, c+1, d+1);
        }

        void print() const {
            dp.print1();
        }
};

struct Input {
    vector<int>& X;     vector<int>& Y; 
    vector<int>& T;     vector<int>& B; 
    vector<int>& L;     vector<int>& R;
};

namespace Subtask124 {
    
    void fillGrid(Array2D<int>& grid) {
        int n = (int)grid.height();
        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);
            }
        }
    }

    vector<ll> solve(   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();

        Array2D<int> grid(n, n, 0);

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

        fillGrid(grid);

        PrefixSum2D<int, ll> ps2d(grid);

        vector<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int a = T[k], b = L[k], c = B[k], d = R[k];
            C[k] = ps2d.rectSum(a, b, c, d);
        }

        return C;
    }

    inline vector<ll> solve(Input& in) {
        return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
    }
};

namespace Subtask3 {
    bool canApply(vector<int>& T, vector<int>& B) {
        int Q = (int)T.size();
        for (int k = 0; k < Q; ++k) {
            if (T[k] != 0  ||  B[k] != 0) return false;
        }
        return true;
    }
    inline bool canApply(Input& in) { return canApply(in.T, in.B); }

    vector<ll> solve(   vector<int>& X, vector<int>& Y,
                        vector<int>& T, vector<int>& B,
                        vector<int>& L, vector<int>& R) 
    {
        int Q = (int)T.size();
        
        PrefixSum1D<int, ll> ps1d(X);

        vector<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int l = L[k], r = R[k];
            C[k] = ps1d.rangeSum(l, r);
        }

        return C;
    }

    inline vector<ll> solve(Input& in) {
        return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
    }
};

namespace Subtask5 {
    bool canApply(vector<int>& X, vector<int>& Y) {
        int n = (int)X.size();
        for (int i = 0; i < n; ++i) {
            if (X[i] != 0  ||  Y[i] != 0) return false;
        }
        return true;
    }
    inline bool canApply(Input& in) { return canApply(in.X, in.Y); }

    vector<ll> solve(   vector<int>& X, vector<int>& Y,
                        vector<int>& T, vector<int>& B,
                        vector<int>& L, vector<int>& R) 
    {
        int Q = (int)T.size();
        
        vector<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int a = T[k], b = L[k], c = B[k], d = R[k];
            if (a == 0) a += 1;
            if (b == 0) b += 1;
            ll area = ((ll)c - a + 1) * (d - b + 1);

            C[k] = area / 2;
            if (area % 2 == 1  &&  (a + b) % 2 == 0) C[k] += 1;
        }

        return C;
    }

    inline vector<ll> solve(Input& in) {
        return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
    }
};

Array2D<int> makeRows(vector<int>& X, vector<int>& Y) {
    int n = X.size();
    Array2D<int> rows(3, n);

    for (int j = 0; j < n; ++j) rows(0, j) = X[j];
    rows(1, 0) = Y[1];  
    rows(2, 0) = Y[2];
    for (int i = 1; i < 3; ++i) {
        for (int j = 1; j < n; ++j) {
            rows(i, j) = (!rows(i-1, j) && !rows(i, j-1));
        }
    }

    return rows;
}

Array2D<int> makeCols(vector<int>& X, vector<int>& Y) {
    int n = X.size();
    Array2D<int> cols(n, 3);

    for (int i = 0; i < n; ++i) cols(i, 0) = Y[i];
    cols(0, 1) = X[1];  
    cols(0, 2) = X[2];
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < 3; ++j) {
            cols(i, j) = (!cols(i-1, j) && !cols(i, j-1));
        }
    }

    return cols;
}

template <typename T, typename S = ll>
class PrefixIndexWeightedSum {
    vector<S> dp;
    PrefixSum1D<T, S> ps;

    public:
        PrefixIndexWeightedSum() = default;

        PrefixIndexWeightedSum(const vector<T>& arr): ps(arr) {   
            build(arr);
        }

        void build(const vector<T>& arr) {
            int n = (int)arr.size();
            dp = vector<S>(n + 1, (S)0);

            for (int i = 1; i <= n; ++i) {
                dp[i] = i * arr[i-1] + dp[i-1];
            }
        }

        // dp: 1-indexed
        S weightedSumOnDp(int l, int r) const {
            return dp[r] - dp[l-1] - (l-1) * ps.rangeSumOnDp(l, r);
        }

        // arr: 0-indexed
        S weightedSum(int l, int r) const {
            if (l > r) return 0;
            return weightedSumOnDp(l + 1, r + 1);
        }

        // void print() {
        //     print(dp);
        // }
};

template <typename T, typename S = ll>
class SuffixIndexWeightedSum {
    PrefixIndexWeightedSum<T, S> piws;
    int n;

    public:
        SuffixIndexWeightedSum() = default;

        SuffixIndexWeightedSum(const vector<T>& arr) {
            n = (int)arr.size();
            vector<T> revArr(n);
            for (int i = 0; i < n; ++i) revArr[i] = arr[n-1-i];

            piws = PrefixIndexWeightedSum<T, S>(revArr);
        }

        // arr: 0-indexed
        S weightedSum(int l, int r) const {
            if (l > r) return 0;
            return piws.weightedSum(n-1 - r, n-1 - l);
        }
};

template <typename T>
class ProjectionGrid {
    vector<T> v;
    int h, w;
    PrefixSum1D<T> ps;
    PrefixIndexWeightedSum<T> piws;
    SuffixIndexWeightedSum<T> siws;

    public:
        ProjectionGrid() = default;
        ProjectionGrid(span<const int> row0, span<const int> col0)
            : h(col0.size()), w(row0.size())
        {
            v.reserve(h + w - 1);
            for (int i = h - 1; i >= 0; --i) 
                v.push_back(col0[i]);

            for (int i = 1; i < w; ++i) 
                v.push_back(row0[i]);

            ps = PrefixSum1D<T>(v);
            piws = PrefixIndexWeightedSum<T>(v);
            siws = SuffixIndexWeightedSum<T>(v);
        }

        inline ll rangeSum(int i, int l, int r) {
            if (l > r) return 0;
            return rangeSumOnVSigned(l - i, r - i);
        }

        ll wideRectSum(int a, int b, int c, int d) {
            return weightedSumOnVSigned(b - c, b - a - 1)
                + (c - a + 1) * rangeSumOnVSigned(b - a, d - c)
                + reverseWeightedSumOnVSigned(d - c + 1, d - a);
        }

        ll tallRectSum(int a, int b, int c, int d) {
            return weightedSumOnVSigned(b - c, d - c - 1)
                + (d - b + 1) * rangeSumOnVSigned(d - c, b - a)
                + reverseWeightedSumOnVSigned(b - a + 1, d - a);
        }

        inline ll rectSum(int a, int b, int c, int d) {
            if (a > c || b > d) return 0;
            
            int h = c - a,  w = d - b;
            if (w >= h) return wideRectSum(a, b, c, d);
            else        return tallRectSum(a, b, c, d);
        }
    
    private:
    // begin rangeSum
        inline ll rangeSumOnV(int l, int r) {
            if (l > r) return 0;
            return ps.rangeSum(l, r);
        }

        inline ll rangeSumOnVSigned(int l, int r) {
            return rangeSumOnV(h-1 + l, h-1 + r);
        }
    // end rangeSum

    // begin weightedSum
        inline ll weightedSumOnV(int l, int r) {
            return piws.weightedSum(l, r);
        }

        inline ll weightedSumOnVSigned(int l, int r) {
            if (l > r) return 0;
            return weightedSumOnV(h-1 + l, h-1 + r);
        }
    // end weightedSum
        
    // begin reverseWeightedSum
        inline ll reverseWeightedSumOnV(int l, int r) {
            return siws.weightedSum(l, r);
        }

        inline ll reverseWeightedSumOnVSigned(int l, int r) {
            if (l > r) return 0;
            return reverseWeightedSumOnV(h-1 + l, h-1 + r);
        }
    // end reverseWeightedSum
};

template <typename T>
class OffsetProjectionGrid {
    ProjectionGrid<T> pGrid;
    int r0, c0;

    public:
        OffsetProjectionGrid() = default;
        OffsetProjectionGrid(span<const int> row0, span<const int> col0, int r0_, int c0_)
            : pGrid(row0, col0), r0(r0_), c0(c0_) {}

        inline ll rangeSum(int i, int l, int r) {
            if (l > r) return 0;
            return pGrid.rangeSum(i - r0, l - c0, r - c0);
        }

        inline ll rectSum(int a, int b, int c, int d) {
            if (a > c || b > d) return 0;
            return pGrid.rectSum(a - r0, b - c0, c - r0, d - c0);
        }
};

namespace Subtask67 {
    bool canApply(vector<int>& T, vector<int>& B) 
    {
        int Q = (int)T.size();

        for (int k = 0; k < Q; ++k) {
            if (T[k] != B[k]) return false;
        }
        return true;
    }
    inline bool canApply(Input& in) { return canApply(in.T, in.B); }
    
    vector<ll> solve(   vector<int>& X, vector<int>& Y,
                        vector<int>& T, vector<int>& B,
                        vector<int>& L, vector<int>& R) 
    {
        int Q = (int)T.size();
    
        auto rows = makeRows(X, Y);
        auto cols = makeCols(X, Y);

        vector<int> row2 = rows.row(2);
        vector<int> col2 = cols.col(2);
        OffsetProjectionGrid<int> offpGrid(  span<int>(row2).subspan(2), 
                                    span<int>(col2).subspan(2), 2, 2);

        PrefixSum1D<int> rowPs[2];
        for (int i = 0; i < 2; ++i) {
            rowPs[i] = PrefixSum1D<int>(rows.row(i));
        }
        
        vector<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int i = T[k], l = L[k], r = R[k];

            if (i < 2) C[k] = rowPs[i].rangeSum(l, r);
            else {
                ll &ans = C[k];
                
                int s = max(l, 0);
                int e = min(r, 1);
                for (int j = s; j <= e; ++j) ans += cols(i, j);
                
                s = max(l, 2);
                e = r;
                ans += offpGrid.rangeSum(i, s, e);   
            }
        }

        return C;
    }

    inline vector<ll> solve(Input& in) {
        return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
    }
};

namespace SubtaskAll {
    
    vector<ll> solve(   vector<int>& X, vector<int>& Y,
                        vector<int>& T, vector<int>& B,
                        vector<int>& L, vector<int>& R) 
    {
        int Q = (int)T.size();
    
        auto rows = makeRows(X, Y);
        auto cols = makeCols(X, Y);

        vector<int> row2 = rows.row(2);
        vector<int> col2 = cols.col(2);
        OffsetProjectionGrid<int> offpGrid( span<int>(row2).subspan(2), 
                                            span<int>(col2).subspan(2), 2, 2);

        PrefixSum1D<int> rowPs[2], colPs[2];
        for (int i = 0; i < 2; ++i) {
            rowPs[i] = PrefixSum1D<int>(rows.row(i));
            colPs[i] = PrefixSum1D<int>(cols.col(i));
        }
        
        vector<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int a = T[k], b = L[k], c = B[k], d = R[k];
            ll &ans = C[k];

            // 1. Top Row Area
            int rs = max(a, 0),
                re = min(c, 1);
            for (int i = rs; i <= re; ++i) ans += rowPs[i].rangeSum(b, d);
            
            // 2. Left Col Area
                rs = max(a, 2),
                re = c;
            int cs = max(b, 0),
                ce = min(d, 1);
            for (int j = cs; j <= ce; ++j) ans += colPs[j].rangeSum(rs, re);

            // 3. Inner Grid Area (by Projection Grid)
                a = max(a, 2),
                b = max(b, 2);
            ans += offpGrid.rectSum(a, b, c, d);
        }

        return C;
    }

    inline vector<ll> solve(Input& in) {
        return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
    }
};

vector<ll> mosaic(vector<int> X, vector<int> Y,
                  vector<int> T, vector<int> B,
                  vector<int> L, vector<int> R) 
{
    int n = (int)X.size();

    Input in{X, Y, T, B, L, R};

    if (n <= 3)
        return Subtask124::solve(in);
    else 
        return SubtaskAll::solve(in);
}

• 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