Submission #1233739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233739		erering	Mosaic (IOI24_mosaic)	C++20	100 / 100	105 ms	46404 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
#include "mosaic.h"
#define pb push_back
const int pls=4e5,N=1e6+5;
#define ll long long
ll pref[N],prefx[pls][2],prefy[pls][2],pref2[N],pref3[N];
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<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=N-1;i>=0;i--){
        pref3[i]=pref[i]*(N-i);
        if(i<N-1)pref3[i]+=pref3[i+1];
    }
    for(int i=0;i<N;i++){
        pref2[i]=pref[i]*(i+1);
        if(i>0)pref2[i]+=pref2[i-1];
    }
    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;
        }
        int pos2=T[i]-L[i]+pls,pos1=T[i]-R[i]+pls;
        if(B[i]-T[i]>R[i]-L[i]){
            sum+=pref2[pos2]-pref2[pos1-1]-(pref[pos2]-pref[pos1-1])*(pos1);
            int l=pos2+1;
            pos2=B[i]-L[i]+pls; pos1=B[i]-R[i]+pls;
            sum+=pref3[pos1]-pref3[pos2+1]-(pref[pos2]-pref[pos1-1])*(N-pos2-1);
            int r=pos1-1;
            if(r>=l)sum+=(pref[r]-pref[l-1])*(R[i]-L[i]+1);
        }
        else{
            pos2=B[i]-R[i]+pls;
            int l=pos2+1;
            sum+=pref2[pos2]-pref2[pos1-1]-(pref[pos2]-pref[pos1-1])*(pos1);
            pos2=B[i]-L[i]+pls; pos1=T[i]-L[i]+pls;
            if(pos1==B[i]-R[i]+pls)pos1++;
            if(pos2>=pos1)sum+=pref3[pos1]-pref3[pos2+1]-(pref[pos2]-pref[pos1-1])*(N-pos2-1);
            int r=pos1-1;
            if(r>=l)sum+=(pref[r]-pref[l-1])*(B[i]-T[i]+1);
        }
        ans.pb(sum);
    }
    return ans;
}
/*
 * 4
1 0 1 0
1 1 0 1
1
0 3 0 3
 */

• 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