Submission #1107942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107942		sleepntsheep	Mosaic (IOI24_mosaic)	C++17	100 / 100	122 ms	30792 KiB

mosaic

#include "mosaic.h"
#include <vector>
#include <array>
#include <cstdio>
#include <algorithm>
#include <cstring>
using ll = long long;
using namespace std;

vector<ll> mosaic(vector<signed> X, vector<signed> Y,
                              vector<signed> T, vector<signed> B,
                              vector<signed> L, vector<signed> R) {
    vector<ll> Ans(T.size());

    int n = (int)X.size(), q = (int)T.size();
    for (int i = 0; i < q; ++i) ++T[i], ++B[i], ++L[i], ++R[i];

    for (auto mode : {'A', 'B'}) {

    static int up[4][1 << 18], left[1 << 18][4];
    memset(up, 0, sizeof up), memset(left, 0, sizeof left);
    for (int i = 1; i <= n; ++i) {
	up[1][i] = X[i - 1], left[i][1] = Y[i - 1];
	if (i <= 3) up[i][1] = Y[i - 1], left[1][i] = X[i - 1];
    }
    for (int k : {2, 3}) for (int i = k; i <= n; ++i) {
	up[k][i] = !up[k - 1][i] && !up[k][i - 1];
	left[i][k] = !left[i - 1][k] && !left[i][k - 1];
	if (i <= 3) up[i][k] |= left[i][k], left[k][i] = up[k][i];
    }

    static int diag_base[1 << 18];
    static ll diag_rig[1 << 18], diag_lef[1 << 18];//, diag_base[1 << 18];
    memset(diag_rig, 0, sizeof diag_rig);
    memset(diag_lef, 0, sizeof diag_lef);
    memset(diag_base, 0, sizeof diag_base);

    for (int i = 1; i + 2 <= n; ++i) {
	diag_base[i] = up[3][i + 2];
	if (mode == 'B') diag_base[1] = 0;
    	diag_rig[i] = diag_base[i] * 1ll * i + diag_rig[i - 1];
	diag_lef[i] = diag_base[i] * 1ll * (n - i) + diag_lef[i - 1];
	diag_base[i] += diag_base[i - 1];
    }

    for (int i = 1; i <= 3; ++i) for (int j = 1; j <= n; ++j) up[i][j] += up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1];
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= 3; ++j) left[i][j] += left[i - 1][j] + left[i][j - 1] - left[i - 1][j - 1];


    for (int i = 0; i < q; ++i) {
	if (T[i] <= 3) {
	    int b = min(B[i], 3);
	    Ans[i] += up[b][R[i]] - up[b][L[i] - 1] - up[T[i] - 1][R[i]] + up[T[i] - 1][L[i] - 1];
	    T[i] = 4; B[i] = max(B[i], 3);
	}
	if (L[i] <= 3) {
	    int r = min(R[i], 3);
	    Ans[i] += left[B[i]][r] - left[T[i] - 1][r] - left[B[i]][L[i] - 1] + left[T[i] - 1][L[i] - 1];
	    L[i] = 4; R[i] = max(R[i], 3);
	}

	if (B[i] < T[i] || R[i] < L[i]) continue;

	ll high = 1 + R[i] - T[i];
	ll mid = L[i] - T[i] + 1;
	ll low = L[i] - B[i] + 1;

	if (high >= 1) {
	if (mid <= 1) {
	    ll ximal = min(high, B[i] - T[i] + 1ll);
	    int pp = high - ximal + 1;
	    Ans[i] += diag_lef[high] - diag_lef[pp - 1] - ((diag_base[high] - diag_base[pp - 1]) * (n - high - 1ll))
				+ (diag_base[pp - 1] * ximal);
	} else {
	    ll ximal = min(high - mid + 1, B[i] - T[i] + 1ll);
		int pp = high - ximal + 1;
		Ans[i] += diag_lef[high] - diag_lef[pp - 1] - ((diag_base[high] - diag_base[pp - 1]) * (n - high - 1ll)) 
				+ (diag_base[pp - 1] - diag_base[mid - 1]) * ximal;

	    ll Low = max(1ll, low);
	    

	    ximal = R[i] - L[i] + 1;
	    if (ximal >= mid - low) {
		Ans[i] += diag_rig[mid - 1] - diag_rig[Low - 1] + ((diag_base[mid - 1] - diag_base[Low - 1]) * (1ll - low));
	    } else {
		int pp = Low + (ximal - min(ximal, Low - low + 1));
		if (pp == Low) Ans[i] += (diag_base[mid - 1] - diag_base[Low - 1]) * ximal;
	else	Ans[i] += diag_rig[pp] - diag_rig[Low - 1] + ((diag_base[pp] - diag_base[Low - 1]) * (1ll - low))
				+ (diag_base[mid - 1] - diag_base[pp]) * ximal;
	    }
	}
	}
	    
	swap(L[i], T[i]), swap(R[i], B[i]);
    }
    swap(X, Y);
    }

    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