Submission #1281454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281454		tuongll	Mosaic (IOI24_mosaic)	C++20	0 / 100	94 ms	30392 KiB

mosaic

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

int add(int a, int b){
    return a == 0 && b == 0;
}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    vector<vector<int>> layers(3);
    int n = X.size(), q = T.size();

    // flatten each layer
    for (int i = n - 1; i >= 0; --i)
        layers[0].push_back(Y[i]);
    for (int i = 1; i < n; ++i)
        layers[0].push_back(X[i]);

    vector<int> pX = X, pY = Y;
    for (int t = 1; t < min(n, 3); ++t){
        vector<int> nX(n - t), nY(n - t);
        nX[0] = nY[0] = add(pX[1], pY[1]);
        for (int i = 1; i < n - t; ++i){
            nX[i] = add(nX[i - 1], pX[i + 1]);
            nY[i] = add(nY[i - 1], pY[i + 1]);
        }

        for (int i = n - t - 1; i >= 0; --i)
            layers[t].push_back(nY[i]);
        for (int i = 1; i < n - t; ++i)
            layers[t].push_back(nX[i]);
        pX.swap(nX), pY.swap(nY);
    }

    // cell (x, y) -> corresponding cell on layer[t] -> correct position in array
    auto mp = [&](int t, int x, int y){
        if (x <= y){
            int d = x - t;
            x = t, y -= d;
        } else {
            int d = y - t;
            y = t, x -= d;
        }

        if (y == t) return n - x - 1;
        else return n + y - 2 * t - 1;
    };

    vector<vector<int>> pref(3);
    for (int t = 0; t < 3; ++t){
        for (int x : layers[t]){
            if (pref[t].empty()) pref[t].push_back(x);
            else pref[t].push_back(pref[t].back() + x);
        }
    }

    // for layers[2], need sth like sum(a[i] * i) and sum(a[i] * (n - i + 1))
    vector<vector<long long>> f(2);
    for (int i = 0; i < (int)layers[2].size(); ++i){
        int val = layers[2][i] * (i + 1);
        if (f[0].empty()) f[0].push_back(val);
        else f[0].push_back(f[0].back() + val);

        val = layers[2][i] * ((int)layers[2].size() - i);
        if (f[1].empty()) f[1].push_back(val);
        else f[1].push_back(f[1].back() + val);
    }

    auto get_sum = [&](int t, int l, int r){
        if (l > r) return 0;
        if (l == 0) return pref[t][r];
        else return pref[t][r] - pref[t][l - 1];
    };

    auto get_sum_inc = [&](int l, int r){
        if (l > r) return 0ll;
        long long s = f[0][r];
        if (l > 0) s -= f[0][l - 1];
        s -= 1ll * l * get_sum(2, l, r);
        return s;
    };
    auto get_sum_dec = [&](int l, int r){
        if (l > r) return 0ll;
        long long s = f[1][r];
        if (l > 0) s -= f[1][l - 1];
        return s - 1ll * ((int)f[1].size() - r - 1) * get_sum(2, l, r);
    };

    vector<long long> ans(q);
    for (int i = 0; i < q; ++i){
        if (T[i] < 2 || L[i] < 2){
            if (T[i] == 0) ans[i] += get_sum(0, mp(0, 0, L[i]), mp(0, 0, R[i]));
            if (T[i] >= 0 && T[i] < 2) ans[i] += get_sum(1, mp(1, 1, max(L[i], 1)), mp(1, 1, R[i]));
            if (L[i] == 0) ans[i] += get_sum(0, mp(0, B[i], 0), mp(0, max(T[i], 1), 0));
            if (L[i] >= 0 && L[i] < 2) ans[i] += get_sum(1, mp(1, B[i], 1), mp(1, max(T[i], 2), 1));

            if (T[i] < 2) T[i] = 2;
            if (L[i] < 2) L[i] = 2;

        }

        if (T[i] > B[i] || L[i] > R[i]) continue;

        int left_most = mp(2, B[i], L[i]), right_most = mp(2, T[i], R[i]);
        int m1 = mp(2, T[i], L[i]), m2 = mp(2, B[i], R[i]);
        // cout << left_most << ' ' << m1 << ' ' << m2 << ' ' << right_most << '\n';

        if (B[i] - T[i] <= R[i] - L[i]){
            ans[i] += 1ll * get_sum(2, m1, m2) * (B[i] - T[i] + 1);
            // cout << get_sum(2, m1, m2) * (B[i] - T[i] + 1) << '\n';
            ans[i] += 1ll * get_sum_inc(left_most, m1 - 1);
            // cout << get_sum_inc(left_most, m1 - 1) << '\n';
            ans[i] += 1ll * get_sum_dec(m2 + 1, right_most);
            // cout << get_sum_dec(m2 + 1, right_most) << '\n';
        } else {
            ans[i] += 1ll * get_sum(2, m2, m1) * (R[i] - L[i] + 1);
            ans[i] += 1ll * get_sum_inc(left_most, m2 - 1);
            ans[i] += 1ll * get_sum_dec(m1 + 1, right_most);
        }
    }

    return ans;
}

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