Submission #1229533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229533		PVM_pvm	Mosaic (IOI24_mosaic)	C++20	100 / 100	96 ms	26952 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
int n;
int prR[MAXN][2];
int prK[MAXN][2];
//set<int> st;
int prefD[2*MAXN];
int imaD[2*MAXN];
long long prefUp[2*MAXN];
long long prefDw[2*MAXN];
long long vzemiUp(int x, int y)
{
    long long suma=prefUp[y];
    if (x!=0) suma-=prefUp[x-1];
    ///y trqbva da e 1
    long long nrm=prefD[y];
    if (x!=0) nrm-=prefD[x-1];
    int sg=2*n-y;
    int rzl=sg-1;
    suma=suma-nrm*rzl;
    return suma;
}
long long vzemiDw(int x, int y)
{
    long long suma=prefDw[y];
    if (x!=0) suma-=prefDw[x-1];
    ///x trqbva da e 1
    long long nrm=prefD[y];
    if (x!=0) nrm-=prefD[x-1];
    int rzl=x;
    suma=suma-nrm*rzl;
    return suma;
}
long long vzemi(int x, int y)
{
    long long suma=prefD[y];
    if (x!=0) suma-=prefD[x-1];
    return suma;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    int Q = (int)T.size();
    n=(int)X.size();
    if (n==1)
    {
        vector<long long> C(Q, X[0]);
        return C;
    }
    else if (n==2)
    {
        int tb[2][2];
        tb[0][0]=X[0];
        tb[0][1]=X[1];
        tb[1][0]=Y[1];
        if (X[1]==0 && Y[1]==0) tb[1][1]=1;
        else tb[1][1]=0;
        vector<long long> C(Q,0);
        for (int q=0;q<Q;q++)
        {
            C[q]=0;
            for (int w=T[q];w<=B[q];w++)
            {
                for (int e=L[q];e<=R[q];e++) C[q]+=tb[w][e];
            }
        }
        return C;
    }
    vector<int> kk2(n);
    kk2[0]=X[1];
    for (int q=1;q<n;q++)
    {
        if (Y[q]==0 && kk2[q-1]==0) kk2[q]=1;
        else kk2[q]=0;
        if (kk2[q]==1)
        {
            ///na q 1 sme
            imaD[q-1+n]=1;
        }
    }
    vector<int> kk3(n);
    kk3[0]=X[2];
    for (int q=1;q<n;q++)
    {
        if (kk2[q]==0 && kk3[q-1]==0) kk3[q]=1;
        else kk3[q]=0;
        if (kk3[q]==1)
        {
            ///na q 2 sme
            imaD[q-2+n]=1;
        }
    }
    prK[0][0]=Y[0];
    for (int q=1;q<n;q++) prK[q][0]=prK[q-1][0]+Y[q];
    prK[0][1]=kk2[0];
    for (int q=1;q<n;q++) prK[q][1]=prK[q-1][1]+kk2[q];
    vector<int> rr2(n);
    rr2[0]=Y[1];
    for (int q=1;q<n;q++)
    {
        if (X[q]==0 && rr2[q-1]==0) rr2[q]=1;
        else rr2[q]=0;
        if (rr2[q]==1)
        {
            ///na 1 q sme
            imaD[1-q+n]=1;
        }
    }
    vector<int> rr3(n);
    rr3[0]=Y[2];
    for (int q=1;q<n;q++)
    {
        if (rr2[q]==0 && rr3[q-1]==0) rr3[q]=1;
        else rr3[q]=0;
        if (rr3[q]==1)
        {
            ///na 2 q sme
            imaD[2-q+n]=1;
        }
    }
    prR[0][0]=X[0];
    for (int q=1;q<n;q++) prR[q][0]=prR[q-1][0]+X[q];
    prR[0][1]=rr2[0];
    for (int q=1;q<n;q++) prR[q][1]=prR[q-1][1]+rr2[q];

    prefD[0]=imaD[0];
    for (int q=1;q<=2*n;q++) prefD[q]=prefD[q-1]+imaD[q];

    prefUp[0]=imaD[0]*2*n;
    for (int q=1;q<=2*n;q++) prefUp[q]=prefUp[q-1]+1LL*imaD[q]*(2*n-q);

    prefDw[0]=imaD[0];
    for (int q=1;q<=2*n;q++) prefDw[q]=prefDw[q-1]+1LL*imaD[q]*(q+1);
    vector<long long> C(Q, 0);
    for (int q=0;q<Q;q++)
    {
        int r1=T[q];
        int r2=B[q];
        int k1=L[q];
        int k2=R[q];
        if (r1<2)
        {
            if (r1==0)
            {
                C[q]+=prR[k2][0];
                if (k1!=0) C[q]-=prR[k1-1][0];
            }
            if (r2!=0)
            {
                C[q]+=prR[k2][1];
                if (k1!=0) C[q]-=prR[k1-1][1];
            }
        }
        if (k1<2)
        {
            if (k1==0)
            {
                C[q]+=prK[r2][0];
                if (r1!=0) C[q]-=prK[r1-1][0];
            }
            if (k2!=0)
            {
                C[q]+=prK[r2][1];
                if (r1!=0) C[q]-=prK[r1-1][1];
            }
        }
        //cout<<"predi1 e "<<C[q]<<"\n";
        if (r1==0 && k1==0) C[q]-=X[0];
        if (r1==0 && (1>=k1 && 1<=k2)) C[q]-=X[1];
        if ((1>=r1 && 1<=r2) && k1==0) C[q]-=Y[1];
        if ((1>=r1 && 1<=r2) && (1>=k1 && 1<=k2)) C[q]-=kk2[1];
        if (r2<2 || k2<2) continue;
        //cout<<"predi e "<<C[q]<<"\n";
        r1=max(r1,2);
        k1=max(k1,2);
        //cout<<r1<<" "<<r2<<" "<<k1<<" "<<k2<<"\n";
        int dr=r2-r1+1;
        int dk=k2-k1+1;
        if (dr==1 && dk==1)
        {
            C[q]+=imaD[r1-k1+n];
        }
        else if (dr<dk)
        {
            int prv=r1-k1+n;
            int psl=r2-k1+n;
            C[q]+=vzemiUp(prv,psl);
            psl=r1-k2+n;
            prv=psl+dr-1;
            C[q]+=vzemiDw(psl,prv);
            if ((dk-dr)>1)
            {
                prv=prv+1;
                psl=r1-k1+n-1;
                C[q]+=1LL*dr*vzemi(prv,psl);
            }
        }
        else
        {
            int prv=r1-k1+n;
            int psl=r1-k2+n;
            C[q]+=vzemiDw(psl,prv);
            //cout<<psl<<" "<<prv<<" "<<C[q]<<"\n";
            if (dr==dk)
            {
                prv++;
                psl=r2-k1+n;
                C[q]+=vzemiUp(prv,psl);
                //cout<<prv<<" "<<psl<<" e quer "<<C[q]<<"\n";
            }
            else
            {
                psl=r2-k1+n;
                prv=psl-dk+1;
                C[q]+=vzemiUp(prv,psl);
                if ((dr-dk)>1)
                {
                    psl=prv-1;
                    prv=r1-k1+n+1;
                    C[q]+=1LL*dk*vzemi(prv,psl);
                }
            }
        }
    }
    return C;
}

• 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