Submission #1204295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204295		perekopskad	Mosaic (IOI24_mosaic)	C++20	22 / 100	254 ms	207996 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 = 5e3 + 100;

ll pref[N][N];

ll f(ll a, ll b) {
    if(a < 0 || b < 0)
        return 0;
    return pref[a][b];
}

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];
        
    fr(i, 0, N - 1)
        pref[i][0] = Y[i];

    fr(i, 1, N - 1) {
        fr(j, 1, N - 1) {
            ll val = pref[i - 1][j] | pref[i][j - 1];
            val ^= 1;
            pref[i][j] = val;
        }
    }

    fr(i, 0, N - 1) {
        fr(j, 0, N - 1) {
            if(i)
                pref[i][j] += pref[i - 1][j];
            if(j)
                pref[i][j] += pref[i][j - 1];
            if(i && j)
                pref[i][j] -= pref[i - 1][j - 1];
        }
    }

    vector <ll> ans(Q);
    fr(i, 0, Q - 1) {
        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: 0 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22