Submission #1203033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203033		Adomas08	Mosaic (IOI24_mosaic)	C++20	0 / 100	90 ms	22080 KiB

mosaic

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

using namespace std;
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 n = X.size(), q = B.size();
    vector <long long> anss;
    int row[3][n], col[3][n];
    for (int i = 0; i < n; i++){
        row[0][i] = X[i];
        col[0][i] = Y[i];
    }
    for (int i = 1; i < 3; i++){
        bool top = Y[i];
        row[i][0] = Y[i];
        for (int j = 1; j < n; j++){
            if (!row[i-1][j] && !top) row[i][j] = 1;
            else row[i][j] = 0;
            top = row[i][j];
        }
    }
    for (int i = 1; i < 3; i++){
        bool top = X[i];
        col[i][0] = X[i];
        for (int j = 1; j < n; j++){
            if (!col[i-1][j] && !top) col[i][j] = 1;
            else col[i][j] = 0;
            top = col[i][j];
        }
    }
    vector <int> ones;
    for (int i = 2; i < n; i++){
        if (row[2][i]){
            ones.push_back(2 - i);
        }
        if (col[2][i] && i != 2){
            ones.push_back(i - 2);
        }
    }
    sort(ones.begin(), ones.end());
    int worthr[3][n], worthc[3][n];
    for (int i = 0; i < 3; i++){
        for (int j = 0; j < n; j++){
            if (j == 0){
                worthr[i][j] = row[i][j];
                worthc[i][j] = col[i][j];
            }
            else{
                worthr[i][j] = worthr[i][j-1] + row[i][j];
                worthc[i][j] = worthc[i][j-1] + col[i][j];
            }
        }
    }
    for (int i = 0; i < q; i++){
        long long ans = 0;
        int t = T[i], b = B[i], l = L[i], r = R[i];
        if (b > 2 && l <= 2){
            int r1 = min(2, r);
            int t1 = max(3, t);
            for (int j = l; j <= r1; j++){
            ans += worthc[j][b] - worthc[j][t1-1];
           }
        }
        if (r > 2 && t <= 2){
            int b1 = min(2, b);
            int l1 = max(3, l);
            for (int j = t; j <= b1; j++){
            ans += worthr[j][r] - worthr[j][l1-1];
           }
        }
        if (l <= 2 && t <= 2){
            int r1 = min(2, r);
            int b1 = min(2, r);
            for (int j = l; j <= r1; j++){
            if (t != 0) ans += worthc[j][b1] - worthc[j][t - 1];
            else ans += worthc[j][b1];
            }
        }
        l = max(l, 3);
        t = max(t, 3);

        int h1 = b - t + 1, l1 = r - l + 1;
        for (auto u : ones){
            if (b - l > u) break;
            if (t - r < u) continue;
            int y = t - u;
            if (y >= l) ans += min(h1, r - y + 1);
            else{
                ans += min(l1, h1 - l + y);
            }

        }
        anss.push_back(ans);
    }
    return anss;
}

• 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