Submission #1217090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217090		hengliao	Mosaic (IOI24_mosaic)	C++20	22 / 100	180 ms	204548 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=5005;

    ll n, q;


    ll a[mxN][mxN];

    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<n;i++){
        a[i][0]=Y[i];
        // pre2[i][0]=b[i][0];
    }
    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<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;
        }
    }
    for(ll i=0;i<n;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];
        }
    }

    vll ans(q);

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

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22