Submission #1214831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214831		biank	모자이크 (IOI24_mosaic)	C++20	100 / 100	101 ms	42692 KiB

mosaic

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

#define sz(x) int(x.size())

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

vi build_next(vi &curr, int first) {
    int n = sz(curr);
    vi nxt(n);
    nxt[0] = first;
    for (int i = 1; i < n; i++) {
        nxt[i] = !nxt[i - 1] && !curr[i];
    }
    return nxt;
}

template<typename T>
vll build_prefix(vector<T> &v) {
    int n = sz(v);
    vll pref(n + 1);
    pref[0] = 0LL;
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + v[i];
    }
    return pref;
}

vll mosaic(vi X, vi Y, vi T, vi B, vi L, vi R) {
    int n = sz(X), q = sz(L);
    int K = min(3, n);
    vector<vi> row(K), col(K);
    row[0] = X, col[0] = Y;
    for (int i = 0; i < K - 1; i++) {
        row[i + 1] = build_next(row[i], Y[i + 1]);
        col[i + 1] = build_next(col[i], X[i + 1]);
    }
    vector<vll> row_prefix(K), col_prefix(K);
    for (int i = 0; i < K; i++) {
        row_prefix[i] = build_prefix(row[i]);
        col_prefix[i] = build_prefix(col[i]);
    }
    int mini = -n + K + 1, maxi = n - K - 1;
    int m = max(0, maxi - mini + 1);
    vi diag(m);
    vll diag2(m), diag3(m);
    for (int diff = mini; diff <= maxi; diff++) {
        int i = diff - mini;
        if (diff < 0) {
            diag[i] = row[K - 1][K - 1 - diff];
        } else {
            diag[i] = col[K - 1][diff + K - 1];
        }
        diag2[i] = (i + 1LL) * diag[i];
        diag3[i] = 1LL * (m - i) * diag[i];
    }
    vll diag_pref = build_prefix(diag);
    vll diag2_pref = build_prefix(diag2);
    vll diag3_pref = build_prefix(diag3);

    auto rectangle_query = [&](int l, int r, int h) {
        if (l > r) return 0LL;
        return (diag_pref[r + 1] - diag_pref[l]) * h;
    };

    auto triangle_query1 = [&](int l, int r) {
        return diag2_pref[r + 1] - diag2_pref[l] - rectangle_query(l, r, l);
    };

    auto triangle_query2 = [&](int l, int r) {
        return diag3_pref[r + 1] - diag3_pref[l] - rectangle_query(l, r, m - 1 - r);
    };

    function<ll(int, int, int, int)> query = [&](int t, int b, int l, int r) {
        if (l > r || t > b) return 0LL;
        if (l < K) return col_prefix[l][b + 1] - col_prefix[l][t] + query(t, b, l + 1, r);
        if (t < K) return row_prefix[t][r + 1] - row_prefix[t][l] + query(t + 1, b, l, r);
        int n = min(b - t + 1, r - l + 1);
        int min_diff = t - r - mini, max_diff = b - l - mini;
        if (b - t == r - l) return triangle_query1(min_diff, min_diff + n - 1) + triangle_query2(min_diff + n, max_diff);
        return triangle_query1(min_diff, min_diff + n - 1) + rectangle_query(min_diff + n, max_diff - n, n) + triangle_query2(max_diff - n + 1, max_diff);
    };

    vll res(q);
    for (int i = 0; i < q; i++) {
        res[i] = query(T[i], B[i], L[i], R[i]);
    }

    return res;
}

• 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