제출 #1228888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228888		12345678	모자이크 (IOI24_mosaic)	C++20	19 / 100	1094 ms	30024 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5, kx=3;

ll n, q, r[nx][kx], qsr[nx][kx], c[kx][nx], qsc[kx][nx], C=3;

ll area(ll a, ll b)
{
    if (a<0||b<0) return 0;
    if (a<2) return qsc[a][b];
    if (b<2) return qsr[a][b];
    ll ans=qsr[a][1]+qsc[1][b]-qsr[1][1];
    //cout<<"prev "<<qsr[a][1]<<' '<<qsc[1][b]<<'\n';
    ll mn=min(a, b)-2, sz=min(a, b)-1;
    //cout<<"here "<<a<<' '<<b<<' '<<mn<<' '<<sz<<' '<<ans<<'\n';
    for (int i=a; i>a-mn; i--) ans+=r[i][2]*(a-i+1);
    for (int i=a-mn; i>=2; i--) ans+=r[i][2]*sz;
    for (int i=b; i>b-mn; i--) ans+=c[2][i]*(b-i+1); 
    for (int i=b-mn; i>=2; i--) ans+=c[2][i]*sz;
    //cout<<"area "<<a<<' '<<b<<' '<<ans-r[2][2]<<'\n';
    return ans-r[2][2]*sz;
}

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) {
    n=X.size(), q=T.size();
    C=min(C, n);
    for (int i=0; i<n; i++) r[i][0]=Y[i], c[0][i]=X[i], qsr[i][0]=r[i][0]+(i?qsr[i-1][0]:0), qsc[0][i]=c[0][i]+(i?qsc[0][i-1]:0);
    for (int i=1; i<C; i++) r[0][i]=X[i], c[i][0]=Y[i], qsr[0][i]=r[0][i]+qsr[0][i-1], qsc[i][0]=c[i][0]+qsc[i-1][0];
    for (int i=1; i<n; i++) for (int j=1; j<C; j++) r[i][j]=!(r[i-1][j]||r[i][j-1]), qsr[i][j]=qsr[i-1][j]+qsr[i][j-1]-qsr[i-1][j-1]+r[i][j];
    for (int i=1; i<C; i++) for (int j=1; j<n; j++) c[i][j]=!(c[i-1][j]||c[i][j-1]), qsc[i][j]=qsc[i-1][j]+qsc[i][j-1]-qsc[i-1][j-1]+c[i][j];
    //for (int i=0; i<n; i++) for (int j=0; j<C; j++) cout<<"qsr "<<i<<' '<<j<<' '<<qsr[i][j]<<'\n';
    std::vector<long long> res(q);
    for (int i=0; i<q; i++) 
    {
        //cout<<"tmp "<<T[i]-1<<' '<<R[i]<<' '<<area(T[i]-1, R[i])<<'\n';
        //cout<<"dbg "<<area(B[i], R[i])<<' '<<area(B[i], L[i]-1)<<' '<<area(T[i]-1, R[i])<<' '<<area(T[i]-1, L[i]-1)<<'\n';
        res[i]=area(B[i], R[i])-area(B[i], L[i]-1)-area(T[i]-1, R[i])+area(T[i]-1, L[i]-1);
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 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