Submission #1313099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313099		joonwu04	Mosaic (IOI24_mosaic)	C++20	59 / 100	286 ms	301924 KiB

mosaic

#include "mosaic.h"
#include <vector>
#include <iostream>
#include <cassert>
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; }

        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;
        
    // dp: 1-indexed
    S sumDp(int l, int r) const {
        return dp[r] - dp[l-1];
    }

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

        // arr: 0-indexed
        S sum(int l, int r) const {
            return sumDp(l+1, r+1);
        }

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

template <typename T, typename S = ll>
class PrefixSum2D {
    Array2D<S> dp;
        
    // dp: 1-indexed
    S sumDp(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);
    }

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

        // grid: 0-indexed
        S sum(int a, int b, int c, int d) const {
            return sumDp(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.sum(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.sum(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);
    }
};

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

        for (int k = 0; k < Q; ++k) {
            if (T[k] != B[k]  ||  L[k] != R[k]) return false;
        }
        return true;
    }
    inline bool canApply(Input& in) { return canApply(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;
    }

    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<ll> C(Q, 0LL);
        for (int k = 0; k < Q; k++) {
            int r = T[k], c = L[k];
            if (r <= 2) C[k] = rows(r, c);
            else if (c <= 2) C[k] = cols(r, c);
            else {
                if (r >= c) {
                    r -= c - 2;
                    c = 2;
                    C[k] = cols(r, c);
                }
                else {
                    c -= r - 2;
                    r = 2;
                    C[k] = rows(r, c);
                }
            }
        }
    
        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();
    int Q = (int)T.size();

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

    if (n <= 5000)
        return Subtask124::solve(in);
    else if(Subtask3::canApply(in))
        return Subtask3::solve(in);
    else if(Subtask5::canApply(in))
        return Subtask5::solve(in);
    else if(Subtask6::canApply(in))
        return Subtask6::solve(in);

    vector<ll> C(Q, 0ll);
    return C;
}

// ____________________________________________

// 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();
//     int Q = (int)T.size();

//     Array2D<int> rows(3, n), cols(n, 3);
    
//     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));
//         }
//     }

//     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));
//         }
//     }

//     vector<ll> C(Q, 0LL);
//     for (int k = 0; k < Q; k++) {
//         int r = T[k], c = L[k];
//         if (r <= 2) C[k] = rows(r, c);
//         else if (c <= 2) C[k] = cols(r, c);
//         else {
//             if (r >= c) {
//                 r -= c - 2;
//                 c = 2;
//                 C[k] = cols(r, c);
//             }
//             else {
//                 c -= r - 2;
//                 r = 2;
//                 C[k] = rows(r, c);
//             }
//         }
//     }

//     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: 0 / 19
• Subtask 8: 0 / 22