제출 #1156384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156384		The_Samurai	모자이크 (IOI24_mosaic)	C++20	60 / 100	1094 ms	41924 KiB

mosaic

#include "mosaic.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

void maxs(int &x, int y) {
    x = max(x, y);
}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, 
                        vector<int> B, vector<int> L, vector<int> R) {

    int n = X.size();
    vector a(n, vector(min(n, 3), false));
    vector pref(max(5, n + 1), vector(5, 0));
    a[0] = vector(n, false);
    for (int i = 0; i < n; i++) {
        a[0][i] = X[i]; a[i][0] = Y[i];
    }
    for (int i = 1; i < n; i++) {
        if (i <= 2) a[i].resize(n);
        for (int j = 1; j < a[i].size(); j++) {
            a[i][j] = !(a[i - 1][j] | a[i][j - 1]);   
        }
    }
    for (int i = 0; i <= 3; i++) pref[i].assign(n + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i].size(); j++) {
            pref[i + 1][j + 1] = a[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
        }
    }
    auto get = [&](int x, int y) -> int {
        assert(min(x, y) >= 2);
        int d = min(x, y) - 2;
        x -= d, y -= d;
        if (y == 2) {
            return n - 1 - x;
        }
        return n - 3 + (y - 2);
    };
    auto sum = [&](int x1, int y1, int x2, int y2) -> int {
        // assert(max(x2, y2) <= 2);
        x1++, x2++, y1++, y2++;
        // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << pref[x2][y2] << endl;
        return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
    };

    vector<int> pref2(n * 3);
    if (n >= 3) {
        int z = 0;
        for (int i = n - 1; i >= 2; i--) {
            pref2[z] = a[i][2];
            if (z > 0) pref2[z] += pref2[z - 1];
            z++;
        }
        for (int i = 3; i < n; i++) {
            pref2[z] = pref2[z - 1];
            pref2[z] += a[2][i];
            z++;
        }
    }

    vector<ll> ans(T.size());
    for (int i = 0; i < T.size(); i++) {
        ll now = 0;
        for (int x = T[i]; x <= min(1, B[i]); x++) {
            auto [y1, y2] = make_pair(L[i], R[i]);
            y1++, y2++;
            now += pref[x+1][y2] - pref[x+1][y1 - 1] - pref[x][y2] + pref[x][y1 - 1];
        }
        auto [x1, x2] = make_pair(T[i], B[i]);
        auto [y1, y2] = make_pair(L[i], R[i]);

        // some small shits
        maxs(x1, 2);
        if (x1 > x2) {
            ans[i] = now;
            continue;
        }
        if (y1 < 2) {
            now += sum(x1, y1, x2, min(1, y2));
            y1 = 2;
        }
        if (y1 > y2) {
            ans[i] = now;
            continue;
        }


        for (int x = x1; x <= x2; x++) {
            int l = get(x, y1), r = get(x, y2);
            now += pref2[r];
            if (l > 0) now -= pref2[l - 1];
        }

        ans[i] = now;


    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < a[i].size(); j++) cout << a[i][j] << ' ';
    //     cout << endl;
    // }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 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