Submission #1233721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233721		erering	Mosaic (IOI24_mosaic)	C++20	60 / 100	1094 ms	23744 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
#include "mosaic.h"
#define pb push_back
const int pls=4e5,N=1e6+5;
int pref[N],prefx[pls][2],prefy[pls][2];
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 a[3][n];
    for(int i=0;i<N;i++)pref[i]=0;
    for(int i=0;i<X.size();i++){
        a[0][i]=X[i];
        prefx[i][0]=X[i];
        if(i>0)prefx[i][0]+=prefx[i-1][0];
    }
    for(int i=1;i<3;i++){
        a[i][0]=Y[i];
        if(i==1)prefx[0][i]=Y[i];
        for(int j=1;j<n;j++){
            if(a[i][j-1]==0 && a[i-1][j]==0){
                a[i][j]=1;
                if(i==2 && j>1)pref[i-j+pls]=1;
            }
            else a[i][j]=0;
            if(i==1)prefx[j][i]=a[i][j]+prefx[j-1][i];
        }
    }
    int b[n][3];
    for(int i=0;i<Y.size();i++){
        b[i][0]=Y[i];
        prefy[i][0]=Y[i];
        if(i>0)prefy[i][0]+=prefy[i-1][0];
    }
    for(int i=1;i<3;i++){
        b[0][i]=X[i];
        if(i==1)prefy[0][i]=Y[i];
        for(int j=1;j<n;j++){
            if(b[j][i-1]==0 && b[j-1][i]==0){
                b[j][i]=1;
                if(i==2 && j>1)pref[j-i+pls]=1;
            }
            else b[j][i]=0;
            if(i==1)prefy[j][i]=b[j][i]+prefy[j-1][i];
        }
    }
    for(int i=1;i<N;i++)pref[i]+=pref[i-1];
    vector<long long> ans;
    for(int i=0;i<T.size();i++){
        long long sum=0;
        while(T[i]<2 && T[i]<=B[i]){
            sum+=prefx[R[i]][T[i]]-(L[i]>0?prefx[L[i]-1][T[i]]:0);
            T[i]++;
        }
        if(T[i]>B[i]){
            ans.pb(sum);
            continue;
        }
        while(L[i]<2 && L[i]<=R[i]){
            sum+=prefy[B[i]][L[i]]-prefy[T[i]-1][L[i]];
            L[i]++;
        }
        if(L[i]>R[i]){
            ans.pb(sum);
            continue;
        }
        while(T[i]<=B[i]){
            int pos2=T[i]-L[i]+pls,pos1=T[i]-R[i]+pls;
            sum+=pref[pos2]-pref[pos1-1];
            T[i]++;
        }
        ans.pb(sum);
    }
    return ans;
}
/*
 * 4
1 0 1 0
1 1 0 1
1
2 2 0 3
 */

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