Submission #1225410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225410		VMaksimoski008	Mosaic (IOI24_mosaic)	C++20	48 / 100	406 ms	47396 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];

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<4; 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<4; 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<4; i++) {
        prefH[i][0] = H[i][0];
        for(int j=1; j<n; j++)
            prefH[i][j] = prefH[i][j-1] + H[i][j];
    }

    map<pii, int> pos;
    vector<int> pref;

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

    for(int i=4; i<n; i++) {
        pref.push_back(H[3][i]);
        if(pref.size() > 1) pref.back() += pref[pref.size()-2];
        pos[{ 3, i }] = id++;
    }

    for(int i=0; i<q; i++) {
        int c1 = l[i], c2 = r[i];
        int r = t[i];
        if(r < 4) {
            ans[i] = prefH[r][c2] - (c1 ? prefH[r][c1-1] : 0);
        } else {
            if(c2 < 4) {
                for(int j=c1; j<=c2; j++) ans[i] += V[r][j];
            } else {
                if(c1 < 4) {
                    for(int j=c1; j<4; j++) ans[i] += V[r][j];
                    c1 = 4;
                }
                int L = pos[_map(r, c1)], R = pos[_map(r, c2)];
                ans[i] += pref[R];
                if(L) ans[i] -= pref[L-1];
            }
        }
    }
    return ans;
}

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