Submission #1204319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204319		perekopskad	Mosaic (IOI24_mosaic)	C++20	100 / 100	632 ms	96360 KiB

mosaic

#include "mosaic.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pii pair <ll, ll>
#define el '\n'
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)

ll const N = 2e5 + 100;

ll pref[2][N], x[3][N], y[N][3];
unordered_map <ll, ll> skip, s1, s2, cnt;

ll f(ll a, ll b) {
    if(!a || !b)
        return 0;

    ll res = 0;

    //[1 - b; a - 1]

    //x - y >= a - b
    //[a - b; a - 1]
    res += (a + 1) * (cnt[a - 1] - cnt[a - b - 1]);
    res -= (s1[a - 1] - s1[a - b - 1]);

    //x - y < a - b
    //[1 - b; a - b - 1]

    res += (b + 1) * (cnt[a - b - 1] - cnt[-b]);
    res -= (s2[a - b - 1] - s2[-b]);

    res -= skip[a - 1] - skip[-b];
    return res;
}

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
    int Q = (int)T.size();
    int N = (int)X.size();

    fr(i, 0, N - 1) {
        pref[0][i] = X[i];
        pref[1][i] = Y[i];

        if(i) {
            pref[0][i] += pref[0][i - 1];
            pref[1][i] += pref[1][i - 1];
        }
    }

    fr(j, 0, N - 1)
        x[0][j] = X[j];
    fr(i, 1, 2) {
        x[i][0] = Y[i];
        fr(j, 1, N - 1) {
            ll val = x[i - 1][j] | x[i][j - 1];
            val ^= 1;
            x[i][j] = val;

            if(!x[i][j] || (i >= 2 && j >= 2 && x[i - 1][j - 1]))
                continue;
            
            skip[i - j] = (i >= 2 && j >= 2);
            s1[i - j] += i - skip[i - j];
            s2[i - j] += j - skip[i - j];
            cnt[i - j]++;
        }
    }

    fr(j, 0, N - 1)
        y[j][0] = Y[j];
    fr(j, 1, 2) {
        y[0][j] = X[j];
        fr(i, 1, N - 1) {
            ll val = y[i - 1][j] | y[i][j - 1];
            val ^= 1;
            y[i][j] = val;

            if(i <= 2 || !y[i][j] || (i >= 2 && j >= 2 && y[i - 1][j - 1]))
                continue;

            skip[i - j] = (i >= 2 && j >= 2);
            s1[i - j] += i - skip[i - j];
            s2[i - j] += j - skip[i - j];
            cnt[i - j]++;
        }
    }

    fr(i, - N - 5, N + 5) {
        skip[i] += skip[i - 1];
        s1[i] += s1[i - 1];
        s2[i] += s2[i - 1];
        cnt[i] += cnt[i - 1];
    }

    vector <ll> ans(Q);
    fr(i, 0, Q - 1) {
        if(T[i] == 0) {
            ans[i] += pref[0][R[i]];
            if(L[i]) ans[i] -= pref[0][L[i] - 1];
            T[i]++;
        }
        if(L[i] == 0) {
            ans[i] += pref[1][B[i]];
            ans[i] -= pref[1][T[i] - 1];
            L[i]++;
        }

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

        ans[i] += f(B[i], R[i]);
        ans[i] -= f(T[i] - 1, R[i]);
        ans[i] -= f(B[i], L[i] - 1);
        ans[i] += f(T[i] - 1, L[i] - 1);
    }


    return ans;
}

• 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