제출 #1245483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245483		Hamed_Ghaffari	Mosaic (IOI24_mosaic)	C++20	12 / 100	78 ms	25548 KiB

mosaic

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

using ll = long long;

const int MXN = 4e5+5;

int X[3][MXN], Y[3][MXN];

ll ps[MXN], ps1[MXN], ps2[MXN];

vector<ll> mosaic(vector<int> X_, vector<int> Y_, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    int n = X_.size(), q = L.size();
    for(int i=0; i<n; i++) X[0][i] = X_[i], Y[0][i] = Y_[i];
    if(n==1) return vector<ll>(q, X[0][0]);
    if(n==2) {
        vector<ll> ans(q, 0);
        for(int i=0; i<q; i++)
            for(int x=T[i]; x<=B[i]; x++)
                for(int y=L[i]; y<=R[i]; y++)
                    ans[i] += (x==1 && y==1 ? !(X[0][1]|Y[0][1]) : (x==0 ? X[0][y] : Y[0][x]));
        return ans;
    }
    X[1][0] = Y[0][1];
    X[2][0] = Y[0][2];
    Y[1][0] = X[0][1];
    Y[2][0] = Y[0][2];
    for(int i=1; i<3; i++)
        for(int j=1; j<n; j++)
            X[i][j] = !(X[i-1][j]|X[i][j-1]),
            Y[i][j] = !(Y[i-1][j]|Y[i][j-1]);
    for(int i=n-1; i>=2; i--)
        ps[2-i+n] += Y[2][i];
    for(int j=3; j<n; j++)
        ps[j-2+n] += X[2][j];
    for(int i=1; i<=2*n-1; i++) {
        ps1[i] = ps1[i-1] + i*ps[i];
        ps2[i] = ps2[i-1] + (2*n-i)*ps2[i-1];
        ps[i] += ps[i-1];
    }
    for(int i=0; i<3; i++)
        for(int j=1; j<n; j++) {
            X[i][j] += X[i][j-1];
            Y[i][j] += Y[i][j-1];
        }
    vector<ll> ans(q, 0);
    for(int i=0; i<q; i++) {
        if(T[i]==0) {
            ans[i] += X[0][R[i]] - (L[i]==0 ? 0 : X[0][L[i]-1]);
            if(B[i]==0) continue;
            T[i]++;
        }
        if(T[i]==1) {
            ans[i] += X[1][R[i]] - (L[i]==0 ? 0 : X[1][L[i]-1]);
            if(B[i]==1) continue;
            T[i]++;
        }
        if(L[i]==0) {
            ans[i] += Y[0][B[i]] - (T[i]==0 ? 0 : Y[0][T[i]-1]);
            if(R[i]==0) continue;
            L[i]++;
        }
        if(L[i]==1) {
            ans[i] += X[1][B[i]] - (T[i]==0 ? 0 : Y[1][T[i]-1]);
            if(R[i]==1) continue;
            L[i]++;
        }
        int mn = L[i]-B[i], mx = R[i]-T[i], len = max(B[i]-T[i], R[i]-L[i])+1;
        ans[i] += ps1[mn+len-2]-ps1[mn-1] - (mn-1)*(ps[mn+len-2]-ps[mn-1])
        + ps2[mx]-ps2[mx-len+1] - (2*n-mx-1)*(ps[mx]-ps[mx-len+1])
        + len*(ps[mx-len+1]-ps[mn+len-2]);
    }
    return ans;
}

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