Submission #1225539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225539		VMaksimoski008	Mosaic (IOI24_mosaic)	C++20	70 / 100	1098 ms	63224 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e5 + 5;

int H[4][N], V[N][4], prefH[4][N], prefV[N][4];

int get(int r, int c) {
    if(r < 4) return H[r][c];
    if(c < 4) return V[r][c];
    if(r <= c) return H[3][c-r+3];
    return V[r-c+3][3];
}

pii _map(int r, int c) {
    int off = min(r, c)-3;
    return { r-off, c-off };
}

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 = t.size();
    vector<ll> ans(q);

    for(int i=0; i<n; i++) {
        H[0][i] = x[i];
        V[i][0] = y[i];
        if(i < 4) H[i][0] = y[i];
        if(i < 4) V[0][i] = x[i];
    }

    for(int i=1; i<min(4, n); i++)
        for(int j=1; j<n; j++)
            H[i][j] = (H[i-1][j] + H[i][j-1] == 0);
    for(int j=1; j<min(4, n); j++)
        for(int i=1; i<n; i++)
            V[i][j] = (V[i-1][j] + V[i][j-1] == 0);

    for(int i=0; i<min(4, n); i++) {
        prefH[i][0] = H[i][0];
        for(int j=1; j<n; j++)
            prefH[i][j] = prefH[i][j-1] + H[i][j];
    }

    for(int j=0; j<min(4, n); j++) {
        prefV[0][j] = V[0][j];
        for(int i=1; i<n; i++)
            prefV[i][j] = prefV[i-1][j] + V[i][j];
    }

    map<pii, int> pos;
    vector<ll> pref, prefL, prefR;
    vector<int> ord;

    int id = 0;
    for(int i=n-1; i>=3; i--) {
        ord.push_back(V[i][3]);
        pos[{ i, 3 }] = id++;
    }

    for(int i=4; i<n; i++) {
        ord.push_back(H[3][i]);
        pos[{ 3, i }] = id++;
    }

    if(n >= 3) {
    pref.push_back(ord[0]);
    for(int i=1; i<ord.size(); i++)
        pref.push_back(pref.back() + ord[i]);
    prefL.push_back(ord[0]);
    for(int i=1; i<ord.size(); i++)
        prefL.push_back(prefL.back() + ord[i] * (i + 1));
    prefR.resize(ord.size()); prefR.back() = ord.back();
    for(int i=ord.size()-2; i>=0; i--)
        prefR[i] = prefR[i+1] + ord[i] * (ord.size() - i);
    prefR.push_back(0);
    }

    // for(int i=0; i<ord.size(); i++) {
    //     cout << pref[i] << " " << prefR[i] << '\n';
    // }

    for(int i=0; i<q; i++) {
        int r1=t[i], r2=b[i], c1=l[i], c2=r[i];
        if(r2 < 4) {
            for(int j=r1; j<=r2; j++)
                ans[i] += prefH[j][c2] - (c1 ? prefH[j][c1-1] : 0);
        } else if(c2 < 4) {
            for(int j=c1; j<=c2; j++)
                ans[i] += prefV[r2][j] - (r1 ? prefV[r1-1][j] : 0);
        } else {
            if(r1 < 4) {
                for(int j=r1; j<4; j++)
                    ans[i] += prefH[j][c2] - (c1 ? prefH[j][c1-1] : 0);
                r1 = 4;
            }

            if(c1 < 4) {
                for(int j=c1; j<4; j++)
                    ans[i] += prefV[r2][j] - (r1 ? prefV[r1-1][j] : 0);
                c1 = 4;
            }

            int L = pos[_map(r2, c1)], R = pos[_map(r1, c2)];
            int mn = min(r2-r1, c2-c1) + 1;

            if(mn >= 2) {
                ans[i] += prefL[L+mn-2] - prefL[L-1];
                ans[i] -= (pref[L+mn-2] - pref[L-1]) * L;
                for(int j=R-mn+2; j<=R; j++)
                    ans[i] += (pref[j] - pref[j-1]) * (R-j+1);
                L += mn - 1;
                R -= mn - 1;
            }

            if(L <= R) {
                ans[i] += pref[R] * mn;
                ans[i] -= pref[L-1] * mn;
            }
        }
    }
    return ans;
}

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