Submission #1217100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217100		hengliao	Mosaic (IOI24_mosaic)	C++20	100 / 100	114 ms	45848 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{
    const ll mxN=2e5+5;

    ll n, q;


    ll a[3][mxN];
    ll b[mxN][3];

    ll pre1[4][mxN], pre2[mxN][4];

    ll val[2*mxN];
    ll pre[2*mxN], pref[2*mxN], pres[2*mxN];

    ll id(ll tar){
        return tar+n-3;
    }
}

vector<long long> mosaic(vector<int> X, vector<int> Y,
                        vector<int> T, vector<int> B,
                        vector<int> L, vector<int> R) {
    memset(pre1, 0, sizeof(pre1));
    memset(pre2, 0, sizeof(pre2));
    n=X.size();
    q=T.size();
    for(ll i=0;i<n;i++){
        a[0][i]=X[i];
        // pre1[0][i]=a[0][i];
    }
    for(ll i=0;i<3;i++){
        a[i][0]=Y[i];
        // pre1[i][0]=a[i][0];
    }
    for(ll i=0;i<n;i++){
        b[i][0]=Y[i];
        // pre2[i][0]=b[i][0];
    }
    for(ll i=0;i<3;i++){
        b[0][i]=X[i];
        // pre2[0][i]=b[0][i];
    }
    if(n<=2){
        for(ll i=1;i<n;i++){
            for(ll j=1;j<n;j++){
                if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
                else a[i][j]=0;
            }
        }
        vll ans(q);
        for(ll i=0;i<q;i++){
            for(ll j=T[i];j<=B[i];j++){
                for(ll k=L[i];k<=R[i];k++){
                    ans[i]+=a[j][k];
                }
            }
        }
        return ans;
    }
    for(ll i=1;i<3;i++){
        for(ll j=1;j<n;j++){
            if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
            else a[i][j]=0;
        }
    }
    for(ll i=1;i<n;i++){
        for(ll j=1;j<3;j++){
            if(b[i-1][j]==0 && b[i][j-1]==0) b[i][j]=1;
            else b[i][j]=0;
        }
    }
    for(ll i=0;i<3;i++){
        for(ll j=0;j<n;j++){
            pre1[i+1][j+1]=pre1[i][j+1]+pre1[i+1][j]-pre1[i][j]+a[i][j];
        }
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<3;j++){
            pre2[i+1][j+1]=pre2[i][j+1]+pre2[i+1][j]-pre2[i][j]+b[i][j];
        }
    }
    for(ll i=n-1;i>=2;i--){
        val[id(i-2)]=b[i][2];
    }
    for(ll i=3;i<n;i++){
        val[id(2-i)]=a[2][i];
    }
    // for(ll i=0;i<=id(n-3);i++){
    //     cout<<i-n+3<<' '<<val[i]<<'\n';
    // }
    pre[0]=0;
    for(ll i=0;i<=id(n-3);i++){
        pre[i+1]=pre[i]+val[i];
    }
    pref[0]=0;
    for(ll i=0;i<=id(n-3);i++){
        pref[i+1]=pref[i]+val[i]+pre[i];
        // cout<<"pref "<<i-n+3<<' '<<pref[i+1]<<'\n';
    }
    pres[id(n-3)+2]=0;
    for(ll i=id(n-3);i>=0;i--){
        pres[i+1]=pres[i+2]+val[i]+pre[id(n-3)+1]-pre[i+1];
    }

    auto nor=[&](ll tar1, ll tar2){
        if(tar1>tar2) return 0LL;
        return pre[tar2+1]-pre[tar1];
    };

    auto ty1=[&](ll tar1, ll tar2){
        if(tar2<tar1) return 0LL;
        ll re=pref[tar2+1]-pref[tar1]-pre[tar1]*(tar2-tar1+1);
        return re;
    };

    auto ty2=[&](ll tar1, ll tar2){
        if(tar2<tar1) return 0LL;
        ll re=pres[tar1+1]-pres[tar2+2]-nor(tar2+1, id(n-3))*(tar2-tar1+1);
        return re;
    };

    auto qry=[&](ll x, ll y){
        if(x<0) return 0LL;
        if(y<0) return 0LL;
        if(x<3){
            return pre1[x+1][y+1];
        }
        if(y<3){
            return pre2[x+1][y+1];
        }
        if(x>=y){
            // cout<<"x, y "<<x<<' '<<y<<'\n';
            ll re=pre1[3][y+1]+pre2[x+1][3]-pre1[3][3];
            // cout<<re<<'\n';
            re+=nor(id(0), id(x-y))*(y-2);
            // cout<<re<<'\n';
            re+=ty1(id(x-y+1), id(x-3));
            // cout<<re<<'\n';
            re+=ty2(id(3-y), id(-1));
            // cout<<re<<'\n';
            return re;
        }
        else{
            // warning
            // cout<<"x, y "<<x<<' '<<y<<'\n';
            ll re=pre1[3][y+1]+pre2[x+1][3]-pre1[3][3];
            // cout<<re<<'\n';
            re+=nor(id(x-y), id(0))*(x-2);
            // cout<<re<<'\n';
            re+=ty1(id(1), id(x-3));
            // cout<<re<<'\n';
            re+=ty2(id(3-y), id(x-y-1));
            // cout<<re<<'\n';
            return re;
        }
    };

    // qry(4, 4);

    // qry(4, 4);
    // qry(4, 1);

    vll ans(q);

    for(ll i=0;i<q;i++){
        ans[i]=qry(B[i], R[i])-qry(T[i]-1, R[i])-
        qry(B[i], L[i]-1)+qry(T[i]-1, L[i]-1);
    }
    return ans;
}

• 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