Submission #1129999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129999		math_rabbit_1028	Mosaic (IOI24_mosaic)	C++20	34 / 100	149 ms	33232 KiB

mosaic

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

vector<int> X2, Y2;
vector<int> diag; // X - Y
vector<int> inv;

int color(int a, int b) {
    if (a == 0 && b == 0) return 1;
    else return 0;
}

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

    if (N == 1) {
        return vector<long long>(Q, X[0]);
    }

    X2.push_back(Y[1]);
    for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
    Y2.push_back(X[1]);
    for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));

    if (color(X2[2], Y2[2]) == 1) {
        for (int i = 0; i <= 2*N; i++) {
            if (abs(i - N) % 2 == 0) diag.push_back(1);
            else diag.push_back(0);
        }

        inv = vector<int>(2*N+1, 0);
        int p = 3;
        while (p < N) {
            if (X[p] == 1) {
                if (p+1 < N && X[p+1] == 1) p += 2;
                else {
                    inv[N-(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }
        p = 3;
        while (p < N) {
            if (Y[p] == 1) {
                if (p+1 < N && Y[p+1] == 1) p += 2;
                else {
                    inv[N+(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }

        for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
        for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
        for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
    }
    else {
        X2.push_back(Y[1]);
        for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
        Y2.push_back(X[1]);
        for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));        
        for (int i = 0; i <= 2*N; i++) {
            if (abs(i - N) % 2 == 1) diag.push_back(1);
            else diag.push_back(0);
        }

        inv = vector<int>(2*N+1, 0);
        int p = 2;
        while (p < N) {
            if (X[p] == 1) {
                if (p+1 < N && X[p+1] == 1) p += 2;
                else {
                    inv[N-(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }
        p = 2;
        while (p < N) {
            if (Y[p] == 1) {
                if (p+1 < N && Y[p+1] == 1) p += 2;
                else {
                    inv[N+(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }

        for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
        for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
        for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
    }

    vector<long long> C(Q, 0);
    vector<long long> Xsum(1, 0), X2sum(1, 0), Ysum(1, 0), Y2sum(1, 0), diagsum(1, 0), idiagsum(1, 0);
    for (int i = 0; i < N; i++) Xsum.push_back(Xsum.back() + X[i]);
    for (int i = 0; i < N; i++) X2sum.push_back(X2sum.back() + X2[i]);
    for (int i = 0; i < N; i++) Ysum.push_back(Ysum.back() + Y[i]);
    for (int i = 0; i < N; i++) Y2sum.push_back(Y2sum.back() + Y2[i]);
    for (int i = 0; i <= N*2; i++) diagsum.push_back(diagsum.back() + diag[i]);
    for (int i = 0; i <= N*2; i++) idiagsum.push_back(idiagsum.back() + (long long)i*diag[i]);
    for (int i = 0; i < Q; i++) {
        if (T[i] == 0) {
            C[i] += Xsum[R[i]+1] - Xsum[L[i]];
            T[i]++;
        }
        if (T[i] > B[i]) continue;
        if (T[i] == 1) {
            C[i] += X2sum[R[i]+1] - X2sum[L[i]];
            T[i]++;
        }
        if (T[i] > B[i]) continue;

        if (L[i] == 0) {
            C[i] += Ysum[B[i]+1] - Ysum[T[i]];
            L[i]++;
        }
        if (L[i] > R[i]) continue;
        if (L[i] == 1) {
            C[i] += Y2sum[B[i]+1] - Y2sum[T[i]];
            L[i]++;
        }
        if (L[i] > R[i]) continue;

        if (B[i] - T[i] > R[i] - T[i]) {
            C[i] += idiagsum[N+T[i]-L[i]] - idiagsum[N+T[i]-R[i]]
                 -  (diagsum[N+T[i]-L[i]] - diagsum[N+T[i]-R[i]]) * (N+T[i]-R[i]-1);
            C[i] += (diagsum[N+B[i]-R[i]+1] - diagsum[N+T[i]-L[i]]) * (R[i]-L[i]+1);
            C[i] += -(idiagsum[N+B[i]-L[i]+1] - idiagsum[N+B[i]-R[i]+1])
                 +  (diagsum[N+B[i]-L[i]+1] - diagsum[N+B[i]-R[i]+1]) * (N+B[i]-L[i]+1);
        }
        else {
            C[i] += idiagsum[N+B[i]-R[i]] - idiagsum[N+T[i]-R[i]]
                 -  (diagsum[N+B[i]-R[i]] - diagsum[N+T[i]-R[i]]) * (N+T[i]-R[i]-1);
            C[i] += (diagsum[N+B[i]-R[i]+1] - diagsum[N+T[i]-L[i]]) * (B[i]-T[i]+1);
            C[i] += -(idiagsum[N+B[i]-L[i]+1] - idiagsum[N+T[i]-L[i]+1])
                 +  (diagsum[N+B[i]-L[i]+1] - diagsum[N+T[i]-L[i]+1]) * (N+B[i]-L[i]+1);
        }
    }

    return C;
}

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