Submission #1248836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248836		qwerasdfzxcl	Mosaic (IOI24_mosaic)	C++20	100 / 100	153 ms	58996 KiB

mosaic

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

using namespace std;
using ll = long long;

vector<ll> a[200200], b[200200];
ll c[2][200200], d[2][200200];
int n;

ll calc(int x, int y){
    if (x <= 3 || y <= 3) return b[x][y];
    
    ll ret = b[x][3] + b[3][y] - b[3][3];
    
    if (x <= y){
        ret += d[1][x] - d[0][x] * (n+1-x);
        ret += c[1][y] - c[0][y] * (n+1-y);
        ret -= c[1][y-x+2] - c[0][y-x+2] * (n+1-y); // n+1 - (y-x+2) - (n+1-y) = x-2
        ret += c[0][y-x+2] * (x-3);
    }

    else{
        ret += c[1][y] - c[0][y] * (n+1-y);
        ret += d[1][x] - d[0][x] * (n+1-x);
        ret -= d[1][x-y+2] - d[0][x-y+2] * (n+1-x); /// n+1 - (x-y+2) - (n+1-x) = y-2
        ret += d[0][x-y+2] * (y-3);
    }

    return ret;
}

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) {
    n = X.size();
    a[0].resize(n+1);
    b[0].resize(n+1);

    for (int i=1;i<=n;i++) a[i].resize(4);
    for (int i=1;i<=3;i++) a[i].resize(n+1);

    for (int j=1;j<=n;j++) a[1][j] = X[j-1];
    for (int i=1;i<=n;i++) a[i][1] = Y[i-1];

    for (int i=2;i<=n;i++){
        for (int j=2;j<(int)a[i].size();j++){
            if (!a[i][j-1] && !a[i-1][j]) a[i][j] = 1;
            else a[i][j] = 0;
        }
    }

    for (int i=1;i<=n;i++){
        b[i].resize(a[i].size());
        for (int j=1;j<(int)a[i].size();j++) b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
    }

    for (int j=3;j<=n;j++){
        c[0][j] = c[0][j-1] + a[3][j];
        c[1][j] = c[1][j-1] + a[3][j] * (n+1-j);
    }

    for (int i=4;i<=n;i++){
        d[0][i] = d[0][i-1] + a[i][3];
        d[1][i] = d[1][i-1] + a[i][3] * (n+1-i);
    }
    
    vector<ll> ans;
    for (int i=0;i<(int)T.size();i++){
        int lx = T[i] + 1, rx = B[i] + 1;
        int ly = L[i] + 1, ry = R[i] + 1;

        ans.push_back(calc(rx, ry) - calc(lx-1, ry) - calc(rx, ly-1) + calc(lx-1, ly-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