Submission #1146689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146689		SpyrosAliv	Mosaic (IOI24_mosaic)	C++20	29 / 100	238 ms	207796 KiB

mosaic

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

int n, q;
vector<int> x, y, a, b, l, r;

vector<ll> solve3() {
    for (int i = 1; i < n; i++) x[i] += x[i-1];
    vector<ll> fin;
    for (int i = 0; i < q; i++) {
        ll ans = x[r[i]];
        if (l[i] > 0) ans -= x[l[i] - 1];
        fin.push_back(ans); 
    }
    return fin;
}

vector<ll> solve124() {
    vector<vector<ll>> grid(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) grid[0][i] = x[i];
    for (int i = 0; i < n; i++) grid[i][0] = y[i];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (grid[i-1][j] || grid[i][j-1]) grid[i][j] = 0;
            else grid[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            if (i > 0) grid[i][j] += grid[i-1][j];
            if (j > 0) grid[i][j] += grid[i][j-1];
            if (i > 0 && j > 0) grid[i][j] -= grid[i-1][j-1];
        }
    }
    vector<ll> ans;
    for (int i = 0; i < q; i++) {
        int curr = grid[b[i]][r[i]];
        if (a[i] > 0) curr -= grid[a[i] - 1][r[i]];
        if (l[i] > 0) curr -= grid[b[i]][l[i] - 1];
        if (a[i] > 0 && l[i] > 0) curr += grid[a[i] - 1][l[i] - 1];
        ans.push_back(curr);
    }
    return ans;
}

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    n = X.size();
    x = X;
    y = Y;
    q = T.size();
    a = T;
    b = B;
    l = L;
    r = R;
    bool sub3 = n > 5000;
    for (int i = 0; i < q; i++) if (a[i] != 0 || b[i] != 0) sub3 = false;
    if (sub3) return solve3();
    if (n <= 5000) return solve124();
    return {-1};
}
/*
int main() {
    vector<ll> k = mosaic({1, 0, 1, 0}, {1, 1, 0, 1}, {0, 2}, {3, 3}, {0, 0}, {3, 2});
    for (auto x: k) cout << x << " ";
}*/

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