Submission #1213927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213927		adaawf	Mosaic (IOI24_mosaic)	C++20	100 / 100	104 ms	27676 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
long long int a[5][200005], b[200005][5], c[200005], d[200005], z;
long long int trya(int x, int y) {
    if (x < 3) return a[x][y];
    if (y < 3) return b[x][y];
    long long int h = a[2][y] + b[x][2] - a[2][2];
    if (x < y) {
        h += d[x];
        h += c[y] - c[y - (x - 3) - 1];
    }
    else {
        h += c[y];
        h += d[x] - d[x - (y - 3) - 1];
    }
    h -= z * (min(x, y) - 2);
    return h;
}
vector<long long int> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> B, vector<int> l, vector<int> r) {
    for (int i = 0; i < x.size(); i++) {
        a[1][i + 1] = x[i];
        if (i < 3) a[i + 1][1] = y[i];
    }
    for (int i = 0; i < y.size(); i++) {
        b[i + 1][1] = y[i];
        if (i < 3) b[1][i + 1] = x[i];
    }
    int n = x.size();
    for (int j = 2; j <= 3; j++) {
        for (int k = 2; k <= n; k++) {
            if (a[j - 1][k] == 0 && a[j][k - 1] == 0) a[j][k] = 1;
            else a[j][k] = 0;
        }
    }
    for (int k = 2; k <= 3; k++) {
        for (int j = 2; j <= n; j++) {
            if (b[j - 1][k] == 0 && b[j][k - 1] == 0) b[j][k] = 1;
            else b[j][k] = 0;
        }
    }
    int h = 0;
    for (int i = 3; i <= n; i++) {
        h += a[3][i];
        c[i] = c[i - 1] + h;
    }
    h = 0;
    for (int i = 3; i <= n; i++) {
        h += b[i][3];
        d[i] = d[i - 1] + h;
    }
    z = a[3][3];
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
        }
    }
    for (int j = 1; j <= 3; j++) {
        for (int i = 1; i <= n; i++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
        }
    }
    vector<long long int> res;
    for (int i = 0; i < t.size(); i++) {
        t[i]++; B[i]++; l[i]++; r[i]++;
        res.push_back(trya(B[i], r[i]) - trya(B[i], l[i] - 1) - trya(t[i] - 1, r[i]) + trya(t[i] - 1, l[i] - 1));
    }
    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