Submission #1228896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228896		12345678	Mosaic (IOI24_mosaic)	C++20	100 / 100	204 ms	36460 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;

struct fenwick
{
    ll f[nx];
    void update(int i, ll vl)
    {
        while (i<n) f[i]+=vl, i+=(i&-i);
    }
    ll query(int i)
    {
        ll tmp=0;
        while (i>0) tmp+=f[i], i-=(i&-i);
        return tmp;
    }
} smr, smc, str, stc;

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];
    ll mn=min(a, b)-2, sz=min(a, b)-1;
    ans+=(str.query(a)-str.query(a-mn))-(n-a-1)*(smr.query(a)-smr.query(a-mn));
    ans+=sz*(smr.query(a-mn)-smr.query(1));
    ans+=(stc.query(b)-stc.query(b-mn))-(n-b-1)*(smc.query(b)-smc.query(b-mn));
    ans+=sz*(smc.query(b-mn)-smc.query(1));
    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=2; i<n; i++) smr.update(i, r[i][2]), smc.update(i, c[2][i]), str.update(i, (n-i)*r[i][2]), stc.update(i, (n-i)*c[2][i]);
    std::vector<long long> res(q);
    for (int i=0; i<q; i++) 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: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 22 / 22