Submission #1224986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224986		LeonidCuk	Mosaic (IOI24_mosaic)	C++20	100 / 100	109 ms	46476 KiB

mosaic

#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
vector<long long> mosaic(vector<int> X,vector<int> Y,vector<int> T,vector<int> B,vector<int> L,vector<int> R)
{
    int n=X.size();
    int m=T.size();
    vector<long long>res;
    if(n<3)
    {
        int v[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0)v[i][j]=X[j];
                else if(j==0)v[i][j]=Y[i];
                else v[i][j]=((v[i-1][j]|v[i][j-1])+1)%2;
            }
        }
        for(int k=0;k<m;k++)
        {
            int sum=0;
            for(int i=T[k];i<=B[k];i++)
            {
                for(int j=L[k];j<=R[k];j++)sum+=v[i][j];
            }
            res.push_back(sum);
        }
        return res;
    }
    else
    {
        long long x1[3][n],y1[n][3],prefx[3][n+1],prefy[n+1][3];
        for(int i=0;i<3;i++)
        {
            prefx[i][0]=0;
            for(int j=0;j<n;j++)
            {
                if(i==0)x1[i][j]=X[j];
                else if(j==0)x1[i][j]=Y[i];
                else x1[i][j]=((x1[i][j-1]|x1[i-1][j])+1)%2;
                prefx[i][j+1]=prefx[i][j]+x1[i][j];
            }
        }
        for(int j=0;j<3;j++)
        {
            prefy[0][j]=0;
            for(int i=0;i<n;i++)
            {
                if(i==0)y1[i][j]=X[j];
                else if(j==0)y1[i][j]=Y[i];
                else y1[i][j]=((y1[i][j-1]|y1[i-1][j])+1)%2;
                prefy[i+1][j]=prefy[i][j]+y1[i][j];
            }
        }
        vector<long long>v(2*n),pv(2*n+1),sv(2*n+1),p1(2*n+1),s1(2*n+1);
        for(int i=2;i<n;i++)
        {
            v[n+i-2]=x1[2][i];
            v[n+2-i]=y1[i][2];
        }
        pv[0]=0;p1[0]=0;s1[2*n]=0;sv[2*n]=0;
        long long k=1;
        for(int i=0;i<2*n;i++)
        {
            pv[i+1]=pv[i]+k*v[i];k++;
            p1[i+1]=p1[i]+v[i];
        }
        k=1;
        for(int i=2*n-1;i>=0;i--)
        {
            sv[i]=sv[i+1]+k*v[i+1];k++;
            s1[i]=s1[i+1]+v[i+1];
        }
        for(int i=0;i<m;i++)
        {
            long long sum=0;
            if(B[i]<=1)
            {
                for(int j=T[i];j<=B[i];j++)
                {
                    sum+=prefx[j][R[i]+1]-prefx[j][L[i]];
                }
                res.push_back(sum);continue;
            }
            if(R[i]<=1)
            {
                for(int j=L[i];j<=R[i];j++)
                {
                    sum+=prefy[B[i]+1][j]-prefy[T[i]][j];
                }
                res.push_back(sum);continue;
            }
            if(T[i]<=1)
            {
                for(int j=T[i];j<2;j++)
                {
                    sum+=prefx[j][R[i]+1]-prefx[j][L[i]];
                }
                T[i]=2;
            }
            if(L[i]<=1)
            {
                for(int j=L[i];j<2;j++)
                {
                    sum+=prefy[B[i]+1][j]-prefy[T[i]][j];
                }
                L[i]=2;
            }
            vector<long long>temp={n+L[i]-B[i],n+L[i]-T[i],n+R[i]-B[i],n+R[i]-T[i]};
            sort(temp.begin(),temp.end());
            long long a=temp[0],b=temp[1],c=temp[2],d=temp[3];
            sum+=pv[b]-pv[a]-(p1[b]-p1[a])*(a);
            sum+=(p1[c+1]-p1[b])*(b-a+1ll);
            sum+=(sv[c]-sv[d])-(s1[c]-s1[d])*(2*n-d);
            res.push_back(sum);
        }
        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