Submission #1245482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245482		Hamed_Ghaffari	Mosaic (IOI24_mosaic)	C++20	20 / 100	89 ms	29256 KiB

mosaic

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

using ll = long long;

const int MXN = 4e5+5;

ll ps[MXN], ps2[MXN], ps3[MXN], psx[MXN], psx1[MXN], psy[MXN], rem[MXN];
int a[3][MXN];

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    int n = X.size(), q = L.size();
    for(int i=0; i<n; i++) {
        a[0][i] = X[i];
        if(i<3) a[i][0] = Y[i];
    }
    psx[1] = X[0];
    for(int i=2; i<=n; i++) psx[i] = psx[i-1] + X[i-1];
    psy[1] = Y[0];
    for(int i=2; i<=n; i++) psy[i] = psy[i-1] + Y[i-1];
    if(n>=2) {
        for(int i=1; i<n; i++)
            a[1][i] = !(a[1][i-1]|a[0][i]);
        psx1[1] = a[1][0];
        for(int i=2; i<=n; i++) psx1[i] = psx1[i-1] + a[1][i-1];
    }

    int fir=-1;
    if(n>=3) {
        for(int i=1; i<n; i++) {
            a[2][i] = !(a[2][i-1]|a[1][i]);
            if(a[2][i]) {
                ps[i-2+n]++;
                if(fir==-1) fir = i;
            }
        }
    }
    for(int i=3; i<n; i++) {
        if(fir!=1) {
            if(Y[i]==0) ps[1-i+n]++, fir=0;
            else if(fir!=2) ps[2-i+n]++, rem[i]++, fir=1;
        }
        fir++;
    }
    for(int i=1; i<n; i++) rem[i] += rem[i-1];
    // for(int i=1; i<=2*n-1; i++) {
    //     cout << ps[i] << ' ';
    // }
    // cout << '\n';
    for(int i=1; i<=2*n-1; i++) {
        ps2[i] = ps2[i-1] + ps[i]*i;
        ps3[i] = ps3[i-1] + ps[i]*(2*n-i);
        ps[i] += ps[i-1];
    }
    vector<ll> ans(q, 0);
    for(int i=0; i<q; i++) {
        if(L[i]==0) {
            ans[i] += psy[B[i]+1] - psy[T[i]];
            if(R[i]==0) continue;
            L[i]++;
        }
        if(T[i]==0) {
            ans[i] += psx[R[i]+1] - psx[L[i]];
            if(B[i]==0) continue;
            T[i]++;
        }
        if(T[i]==1) {
            ans[i] += psx1[R[i]+1] - psx1[L[i]];
            if(B[i]==1) continue;
            T[i]++;
        }
        if(L[i]==1) ans[i] -= rem[B[i]] - rem[T[i]-1];
        // cout << T[i] << ' ' << B[i] << ' ' << L[i] << ' ' << R[i] << '\n';
        int mn = L[i]-B[i]+n, mx = R[i]-T[i]+n, len = min(B[i]-T[i], R[i]-L[i])+1;
        // cout << mn << ' ' << mx << ' ' << len << '\n';
        // cout << mx-len+1 << ' ' << mn+len-2 << '\n';
        // cout << ps[mx-len+1] << ' ' << ps[mn+len-2] << '\n';
        ans[i] += 
            (ps2[mn+len-2]-ps2[mn-1])-(mn-1)*(ps[mn+len-2]-ps[mn-1])
        +   (ps3[mx]-ps3[mx-len+1])-(2*n-1-mx)*(ps[mx]-ps[mx-len+1])
        +   len*(ps[mx-len+1]-ps[mn+len-2]);
    }
    return ans;
}

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