Submission #1254768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254768		Rainmaker2627	Mosaic (IOI24_mosaic)	C++20	15 / 100	90 ms	25416 KiB

mosaic

#include "mosaic.h"

#include <vector>

std::vector<long long> preX, preY, preL, sufR, preD;
long long query(int N, int T, int B, int L, int R) {
    long long ans=0;
    if (T==0) {
        T=1;
        ans+=preX[R+1]-preX[L];
        if (B==0) return ans;
    }
    if (L==0) {
        L=1;
        ans+=preY[B+1]-preY[T];
        if (R==0) return ans;
    }

    if (R-B<L-T) {
        ans+=(preL[R-B+N-1]-preL[L-B+N-2])-(preD[R-B+N-1]-preD[L-B+N-2])*(L-B+N-2);
        ans+=(sufR[L-T+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[L-T+N-2])*(N-2+T-R);
        ans+=(R-L+1)*(preD[L-T+N-2]-preD[R-B+N-1]);
    } else if (R-B>L-T) {
        ans+=(preL[L-T+N-1]-preL[L-B+N-2])-(preD[L-T+N-1]-preD[L-B+N-2])*(L-B+N-2);
        ans+=(sufR[R-B+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[R-B+N-2])*(N-2+T-R);
        ans+=(B-T+1)*(preD[R-B+N-2]-preD[L-T+N-1]);
    } else {
        ans+=(preL[L-T+N-2]-preL[L-B+N-2])-(preD[L-T+N-2]-preD[L-B+N-2])*(L-B+N-2);
        ans+=(sufR[R-B+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[R-B+N-2])*(N-2+T-R);
    } return ans;
}

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
    int N = (int) X.size();
    int Q = (int)T.size();
    std::vector<long long> C(Q, 0);

    std::vector<int> diag(2*N-2);
    diag[N-2]=1-(X[1]|Y[1]);
    for (int i = N-1; i < 2*N-3; i++) diag[i]=1-(diag[i-1]|X[i-N+3]);
    for (int i = N-3; i >= 0; i--) diag[i]=1-(diag[i+1]|Y[N-1-i]);
    
    preX.assign(N+2, 0);
    preY.assign(N+2, 0);
    for (int i = 1; i <= N; i++) {
        preX[i]=preX[i-1]+X[i-1];
        preY[i]=preY[i-1]+Y[i-1];
    }

    preL.assign(2*N-1, 0);
    sufR.assign(2*N-1, 0);
    preD.assign(2*N-1, 0);
    for (int i = 1; i <= 2*N-3; i++) {
        preL[i]=preL[i-1]+i*diag[i-1];
        sufR[2*N-3-i]=sufR[2*N-2-i]+i*diag[2*N-3-i];
        preD[i]=preD[i-1]+diag[i-1];
    }
    
    for (int i = 0; i < Q; i++) {
        C[i]=query(N, T[i], B[i], L[i], R[i]);
    }

    return C;
}

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