Submission #1203250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203250		AlgorithmWarrior	Mosaic (IOI24_mosaic)	C++20	100 / 100	98 ms	31048 KiB

mosaic

#include <bits/stdc++.h>

using namespace std;

vector<long long>subtask3(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
    int n=X.size();
    vector<int>sp(n+5,0);
    int i;
    for(i=1;i<=n;++i)
        sp[i]=sp[i-1]+X[i-1];
    int q=T.size();
    vector<long long>answer;
    for(i=0;i<q;++i){
        int left=L[i]+1;
        int right=R[i]+1;
        answer.push_back(sp[right]-sp[left-1]);
    }
    return answer;
}

vector<long long>subtask4(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
    int n=X.size();
    vector<vector<bool>>mat(n+5,vector<bool>(n+5,0));
    vector<vector<int>>sp(n+5,vector<int>(n+5,0));
    int i,j;
    for(j=1;j<=n;++j)
        mat[1][j]=X[j-1];
    for(i=1;i<=n;++i)
        mat[i][1]=Y[i-1];
    for(i=2;i<=n;++i)
        for(j=2;j<=n;++j)
            mat[i][j]=((!mat[i-1][j] && !mat[i][j-1])?1:0);
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+mat[i][j];
    vector<long long>answer;
    int q=T.size();
    for(i=0;i<q;++i){
        int top=T[i]+1;
        int bottom=B[i]+1;
        int left=L[i]+1;
        int right=R[i]+1;
        answer.push_back(sp[bottom][right]-sp[bottom][left-1]-sp[top-1][right]+sp[top-1][left-1]);
    }
    return answer;
}

vector<long long>subtask5(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
    int q=T.size();
    int i;
    vector<long long>answer;
    for(i=0;i<q;++i){
        int top=T[i];
        int bottom=B[i];
        int left=L[i];
        int right=R[i];
        top=max(top,1);
        left=max(left,1);
        if(top>bottom || left>right)
            answer.push_back(0);
        else{
            long long arie=1LL*(bottom-top+1)*(right-left+1);
            int first_val=(top+left+1)%2;
            if(arie&1 && first_val)
                answer.push_back(arie/2+1);
            else
                answer.push_back(arie/2);
        }
    }
    return answer;
}

int get_diag(int x,int y,int n){
    return n-x+y;
}

vector<long long>subtask6(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
    int n=X.size();
    vector<bool>lin[3];
    vector<bool>col[3];
    int i;
    for(i=0;i<3;++i){
        lin[i].resize(n+5,0);
        col[i].resize(n+5,0);
    }
    for(i=0;i<n;++i)
        lin[0][i]=X[i];
    for(i=0;i<n;++i)
        col[0][i]=Y[i];
    lin[1][0]=col[0][1];
    lin[2][0]=col[0][2];
    col[1][0]=lin[0][1];
    col[2][0]=lin[0][2];
    for(i=1;i<n;++i){
        lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
        lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
        col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
        col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
    }
    vector<bool>diag(2*n+5,0);
    for(i=2;i<n;++i)
        if(lin[2][i])
            diag[get_diag(2,i,n)]=1;
    for(i=2;i<n;++i)
        if(col[2][i])
            diag[get_diag(i,2,n)]=1;
    int q=T.size();
    vector<long long>answer;
    for(i=0;i<q;++i){
        int l=T[i];
        int c=L[i];
        if(l<3){
            answer.push_back(lin[l][c]);
        }
        else
        if(c<3){
            answer.push_back(col[c][l]);
        }
        else{
            answer.push_back(diag[get_diag(l,c,n)]);
        }
    }
    return answer;
}

int bin_search(vector<int>&diag,int val){
    ///prima val care il intrece sau e egal
    int l=-1,r=diag.size()-1;
    /// (l r]
    while(r-l>1){
        int mid=(l+r)/2;
        if(diag[mid]>=val)
            r=mid;
        else
            l=mid;
    }
    return r;
}

vector<long long>subtask7(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
    int n=X.size();
    vector<bool>lin[3];
    vector<bool>col[3];
    int i;
    for(i=0;i<3;++i){
        lin[i].resize(n+5,0);
        col[i].resize(n+5,0);
    }
    for(i=0;i<n;++i)
        lin[0][i]=X[i];
    for(i=0;i<n;++i)
        col[0][i]=Y[i];
    lin[1][0]=col[0][1];
    lin[2][0]=col[0][2];
    col[1][0]=lin[0][1];
    col[2][0]=lin[0][2];
    for(i=1;i<n;++i){
        lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
        lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
        col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
        col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
    }
    vector<int>diag;
    for(i=n-1;i>2;--i)
        if(col[2][i])
            diag.push_back(get_diag(i,2,n));
    for(i=2;i<n;++i)
        if(lin[2][i])
            diag.push_back(get_diag(2,i,n));
    vector<int>splin[3];
    vector<int>spcol[3];
    int j;
    for(i=0;i<3;++i){
        splin[i].resize(n+5,0);
        spcol[i].resize(n+5,0);
    }
    for(i=0;i<3;++i){
        splin[i][0]=lin[i][0];
        spcol[i][0]=col[i][0];
        for(j=1;j<n;++j){
            splin[i][j]=splin[i][j-1]+lin[i][j];
            spcol[i][j]=spcol[i][j-1]+col[i][j];
        }
    }
    int q=T.size();
    vector<long long>answer;
    diag.push_back(2e9);
    for(i=0;i<q;++i){
        int top=T[i];
        int bottom=B[i];
        int left=L[i];
        int right=R[i];
        if(top<3){
            answer.push_back(splin[top][right]-splin[top][left-1]);
        }
        else{
            int cnt=0;
            if(left<=0 && 0<=right){
                cnt+=col[0][top];
                ++left;
            }
            if(left<=1 && 1<=right){
                cnt+=col[1][top];
                ++left;
            }
            if(left>right)
                answer.push_back(cnt);
            else{
                int ind1=bin_search(diag,get_diag(top,left,n));
                int ind2=bin_search(diag,get_diag(top,right,n)+1);
                answer.push_back(ind2-ind1+cnt);
            }
        }
    }
    return answer;
}

long long spdst(int d1,int d2,vector<int>&cnt,vector<long long>&sum){
    return sum[d2]-sum[d1-1]-1LL*cnt[d1-1]*(d2-d1+1);
}

long long spddr(int d1,int d2,vector<int>&cnt,vector<long long>&sum){
    return sum[d1]-sum[d2+1]-1LL*cnt[d2+1]*(d2-d1+1);
}

long long get_answer(int top,int bottom,int left,int right,int n,vector<int>&cntst,vector<int>&cntdr,vector<long long>&sumst,vector<long long>&sumdr){
    if(bottom-left>right-left){
        int diag1=get_diag(top,left,n);
        int diag2=get_diag(bottom,right,n);
        int diag3=get_diag(top,right,n);
        int diag4=get_diag(bottom,left,n);
        return 1LL*(right-left+1)*(cntst[diag1]-cntst[diag2-1])+spdst(diag1+1,diag3,cntst,sumst)+spddr(diag4,diag2-1,cntdr,sumdr);
    }
    else{
        int diag1=get_diag(top,left,n);
        int diag2=get_diag(bottom,right,n);
        int diag3=get_diag(top,right,n);
        int diag4=get_diag(bottom,left,n);
        return 1LL*(bottom-top+1)*(cntst[diag2]-cntst[diag1-1])+spdst(diag2+1,diag3,cntst,sumst)+spddr(diag4,diag1-1,cntdr,sumdr);
    }
}

vector<long long>subtask8(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
    int n=X.size();
    vector<bool>lin[3];
    vector<bool>col[3];
    int i;
    for(i=0;i<3;++i){
        lin[i].resize(n+5,0);
        col[i].resize(n+5,0);
    }
    for(i=0;i<n;++i)
        lin[0][i]=X[i];
    for(i=0;i<n;++i)
        col[0][i]=Y[i];
    lin[1][0]=col[0][1];
    lin[2][0]=col[0][2];
    col[1][0]=lin[0][1];
    col[2][0]=lin[0][2];
    for(i=1;i<n;++i){
        lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
        lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
        col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
        col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
    }
    vector<int>splin[3];
    vector<int>spcol[3];
    int j;
    for(i=0;i<3;++i){
        splin[i].resize(n+5,0);
        spcol[i].resize(n+5,0);
    }
    for(i=0;i<3;++i){
        splin[i][0]=lin[i][0];
        spcol[i][0]=col[i][0];
        for(j=1;j<n;++j){
            splin[i][j]=splin[i][j-1]+lin[i][j];
            spcol[i][j]=spcol[i][j-1]+col[i][j];
        }
    }
    vector<bool>diag(2*n+5,0);
    for(i=2;i<n;++i)
        if(lin[2][i])
            diag[get_diag(2,i,n)]=1;
    for(i=2;i<n;++i)
        if(col[2][i])
            diag[get_diag(i,2,n)]=1;
    vector<int>cntst(2*n+5,0);
    vector<int>cntdr(2*n+5,0);
    vector<long long>sumst(2*n+5,0);
    vector<long long>sumdr(2*n+5,0);
    for(i=0;i<2*n+5;++i){
        cntst[i]=cntst[i-1]+diag[i];
        sumst[i]=sumst[i-1]+cntst[i];
    }
    for(i=2*n+4;i>=0;--i){
        cntdr[i]=cntdr[i+1]+diag[i];
        sumdr[i]=sumdr[i+1]+cntdr[i];
    }
    int q=T.size();
    vector<long long>answer;
    for(i=0;i<q;++i){
        int top=T[i];
        int bottom=B[i];
        int left=L[i];
        int right=R[i];
        int cnt=0;
        if(top==0){
            cnt+=splin[0][right]-((left)?splin[0][left-1]:0);
            ++top;
        }
        if(top>bottom){
            answer.push_back(cnt);
            continue;
        }
        if(top==1){
            cnt+=splin[1][right]-((left)?splin[1][left-1]:0);
            ++top;
        }
        if(top>bottom){
            answer.push_back(cnt);
            continue;
        }
        if(left==0){
            cnt+=spcol[0][bottom]-((top)?spcol[0][top-1]:0);
            ++left;
        }
        if(left>right){
            answer.push_back(cnt);
            continue;
        }
        if(left==1){
            cnt+=spcol[1][bottom]-((top)?spcol[1][top-1]:0);
            ++left;
        }
        if(left>right){
            answer.push_back(cnt);
            continue;
        }
        answer.push_back(get_answer(top,bottom,left,right,n,cntst,cntdr,sumst,sumdr)+cnt);
    }
    return answer;
}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
    return subtask8(X,Y,T,B,L,R);
}

• 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