Submission #1216218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216218		mariza	Mosaic (IOI24_mosaic)	C++20	0 / 100	1100 ms	135080 KiB

mosaic

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

typedef long long ll;
const ll N=1e6;
const ll N5=2e5;

map<ll,ll> pref0, pref1, pref2, prefr[2], prefc[2];

ll sum0(ll l, ll r){
    return pref0[r]-pref0[l-1];
}

ll sum1(ll l, ll r){
    return pref1[r]-pref1[l-1]-l*sum0(l,r);
}

ll sum2(ll l, ll r){
    return pref2[r]-pref2[l-1]-(N-r-1)*sum0(l,r);
}

ll sumr(ll l, ll r, ll i){
    return prefr[i][r]-prefr[i][l-1];
}

ll sumc(ll l, ll r, ll i){
    return prefc[i][r]-prefc[i][l-1];
}

ll d(ll i, ll j) {return j-i;}

bool val(bool a, bool b) {return (!a) && (!b);}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    ll n=X.size(), q=T.size();

    while(n<3){
        X.push_back(0);
        Y.push_back(0);
        n++;
    }

    prefr[0][0]=X[0];
    prefr[1][0]=Y[1];
    for(ll i=1; i<n; i++){
        prefr[0][i]=X[i];
        prefr[1][i]=val(prefr[1][i-1],prefr[0][i]);
    }

    prefc[0][0]=Y[0];
    prefc[1][0]=X[1];
    for(ll i=1; i<n; i++){
        prefc[0][i]=Y[i];
        prefc[1][i]=val(prefc[1][i-1],prefc[0][i]);
    }

    pref0[d(2,2)]=val(prefr[1][2],prefc[1][2]);
    for(ll i=3; i<n; i++){
        pref0[d(2,i)]=val(pref0[d(2,i-1)],prefr[1][i]);
        pref0[d(i,2)]=val(pref0[d(i-1,2)],prefc[1][i]);
    }

    for(auto i:pref0){
        pref1[i.first]=(i.first+1)*i.second;
        pref2[i.first]=(n-i.first)*i.second;
    }

    for(ll i=1; i<n; i++){
        prefr[0][i]+=prefr[0][i-1];
        prefr[1][i]+=prefr[1][i-1];
        prefc[0][i]+=prefc[0][i-1];
        prefc[1][i]+=prefc[1][i-1];
    }

    for(ll i=3-n; i<=n-2; i++){
        pref0[i]+=pref0[i-1];
        pref1[i]+=pref1[i-1];
        pref2[i]+=pref2[i-1];
    }

    vector<ll> ANS;
    for(ll Q=0; Q<q; Q++){
        ll t=T[Q], b=B[Q], l=L[Q], r=R[Q];

        ll ans=0;

        if(t==0){
            ans+=sumr(l,r,0);
            t++;
        }
        if(t==1){
            ans+=sumr(l,r,1);
            t++;
        }

        if(l==0){
            ans+=sumc(t,b,0);
            l++;
        }
        if(l==1){
            ans+=sumc(t,b,1);
            l++;
        }

        ll x=r-l+1, y=b-t+1, z=min(x,y);
        ans+=sum1(d(b,l),d(b-z+2,l))+z*sum0(d(b-z+1,l),d(t,r-z+1))+sum2(d(t,r-z+2),d(t,r));
        ANS.push_back(ans);
    }
    return ANS;
}

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