Submission #1105677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105677		Zicrus	Mosaic (IOI24_mosaic)	C++17	100 / 100	123 ms	51984 KiB

mosaic

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

typedef long long ll;

ll n, q;
vector<vector<ll>> lay, layPref;
vector<ll> stairs;

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    n = X.size();
    q = T.size();
    lay = vector<vector<ll>>(5, vector<ll>(2*n-1));
    layPref = vector<vector<ll>>(5, vector<ll>(2*n));
    stairs = vector<ll>(2*n);
    vector<ll> res(q);
    for (int i = 0; i < n; i++) {
        lay[0][n-1+i] = X[i];
        lay[0][n-1-i] = Y[i];
    }
    for (int L = 1; L < min(5ll, n); L++) {
        ll mid = n-1-L;
        lay[L][mid] = !lay[L-1][mid] && !lay[L-1][mid+2];
        for (int i = mid+1; i < 2*n-1-2*L; i++) {
            lay[L][i] = !lay[L][i-1] && !lay[L-1][i+2];
        }
        for (int i = mid-1; i >= 0; i--) {
            lay[L][i] = !lay[L][i+1] && !lay[L-1][i];
        }
    }
    for (int L = 0; L < min(5ll, n); L++) {
        for (int i = 0; i < 2*n-1-2*L; i++) {
            layPref[L][i+1] = layPref[L][i] + lay[L][i];
        }
    }
    if (n >= 5) {
        for (int i = 0; i < 2*n-1; i++) {
            stairs[i+1] = stairs[i] + (i+1)*lay[4][i];
        }
    }

    // Solve
    for (int k = 0; k < q; k++) {
        ll t = T[k], b = B[k], l = L[k], r = R[k];
        ll ans = 0;
        bool skip = false;
        while (t < 5 || l < 5) {
            if (t < l) { // Move t
                ll L = t;
                ll mid = n-1-L;
                ll ref = mid-L;
                ll idL = ref + l;
                ll idR = ref + r;
                ans += layPref[L][idR+1] - layPref[L][idL];
                t++;
            }
            else { // Move l
                ll L = l;
                ll idL = n-1-b;
                ll idR = n-1-t;
                ans += layPref[L][idR+1] - layPref[L][idL];
                l++;
            }

            // Check if done
            if (b-t < 0 || r-l < 0) {
                skip = true;
                break;
            }
        }

        if (skip) {
            res[k] = ans;
            continue;
        }

        // Get remaining area
        ll idBL = n-1-b + l-4;
        ll idBR = n-1-b + r-4;
        ll idTL = n-1-t + l-4;
        ll idTR = n-1-t + r-4;

        ll idL = min(idTL, idBR);
        ll idR = max(idTL, idBR);
        ll idLL = idBL;
        ll idRR = idTR;
        ll w = min(b-t+1, r-l+1);
        
        ans += (layPref[4][idR+1] - layPref[4][idL]) * w; // middle
        ans += stairs[idL] - stairs[idLL] - (layPref[4][idL] - layPref[4][idLL])*idLL; // left
        ll rightStair = stairs[idRR+1] - stairs[idR+1] - (layPref[4][idRR+1] - layPref[4][idR+1])*(idR+1);
        ans += (layPref[4][idRR+1] - layPref[4][idR+1])*(idRR-idR+1) - rightStair; // right

        res[k] = ans;
    }
    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

• 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