제출 #1132488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132488		alterio	모자이크 (IOI24_mosaic)	C++20	100 / 100	566 ms	70956 KiB

mosaic

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

using namespace std;

#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5 + 100;

ll X[3][mxn], Y[mxn][3], prfX[3][mxn], prfY[mxn][3], prf[3 * mxn], suf[3 * mxn], val[3 * mxn], RP[3 * mxn], DP[3 * mxn];

// x - vertical, y - horizontal

ll getSQ(int x, int y) {
	if (x < 0 || y < 0) return 0;
	if (x <= 2) return X[x][y];
	if (y <= 2) return Y[x][y];
	if (x < y) return X[2][y - (x - 2)];
	return Y[x - (y - 2)][2];
}

map<pair<int, int>, int> comp;

ll f(int x, int y) {
	return comp[{x, y}];
}

ll trim(int x1, int x2, int y1, int y2) {
	ll res = 0;
	for (int i = y1; i < 2; i++) {
		res += prfY[x2][i] - (x1 == 0 ? 0 : prfY[x1 - 1][i]);
	}
	y1 = max(y1, 2);
	for (int i = x1; i < 2; i++) {
		res += prfX[i][y2] - (y1 == 0 ? 0 : prfX[i][y1 - 1]);
	}
	return res;
}

ll get(int x, int y) {
	if (x < y) return f(2, y - (x - 2));
	return f(x - (y - 2), 2);
}

ll special(int x1, int x2, int y1, int y2) {
	ll ans = 0;
	if (x2 <= 2) {
		for (int i = x1; i <= x2; i++) {
			ans += prfX[i][y2] - (y1 == 0 ? 0 : prfX[i][y1 - 1]);
		}
	}
	else if (y2 <= 2) {
		for (int i = y1; i <= y2; i++) {
			ans += prfY[x2][i] - (x1 == 0 ? 0 : prfY[x1 - 1][i]);
		}
	}
	return ans;
}

ll getP(int x, int y) {
	if (x > y) return 0;
	return prf[y] - (x == 0 ? 0 : prf[x - 1]);
}

ll cnt;

ll getS(int x, int y) {
	if (x > y) return 0;
	return suf[x] - (y == cnt - 1 ? 0 : suf[y + 1]);
}

vector<ll> mosaic(vector<int> _X, vector<int> _Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    int n = _X.size();
    int q = T.size();
    vector<ll> C(q, 0);
    for (int i = 0; i < n; i++) {
		X[0][i] = _X[i], Y[i][0] = _Y[i];
		prfX[0][i] = (i > 0 ? prfX[0][i - 1] : 0) + X[0][i];
		prfY[i][0] = (i > 0 ? prfY[i - 1][0] : 0) + Y[i][0];
	}
    for (int i = 1; i < 3; i++) {
		X[i][0] = Y[i][0];
		prfX[i][0] = X[i][0];
		for (int j = 1; j < n; j++) {
			X[i][j] = (!X[i][j - 1] && !X[i - 1][j]);
			prfX[i][j] = prfX[i][j - 1] + X[i][j];
		}
    }
	for (int i = 1; i < 3; i++) {
		Y[0][i] = X[0][i];
		prfY[0][i] = Y[0][i];
		for (int j = 1; j < n; j++) {
			Y[j][i] = (!Y[j][i - 1] && !Y[j - 1][i]);
			prfY[j][i] = prfY[j - 1][i] + Y[j][i];
		}
	}
	for (int i = n - 1; i >= 2; i--) {
		prf[cnt] = (cnt > 0 ? prf[cnt - 1] : 0) + Y[i][2];
		val[cnt] = Y[i][2];
		comp[{i, 2}] = cnt++;
	}
	for (int i = 3; i < n; i++) {
		prf[cnt] = prf[cnt - 1] + X[2][i];
		val[cnt] = X[2][i];
		comp[{2, i}] = cnt++;
	}
	for (int i = 0; i < cnt; i++) {
		RP[i] = (i > 0 ? RP[i - 1] : 0) + (i + 1) * val[i];
	}
	for (int i = cnt - 1; i >= 0; i--) {
		suf[i] = (i < cnt - 1 ? suf[i + 1] : 0) + val[i];
		DP[i] = (i < cnt - 1 ? DP[i + 1] : 0) + (cnt - i) * val[i];
	}
	for (int i = 0; i < q; i++) {
		if (R[i] <= 2 || B[i] <= 2) C[i] = special(T[i], B[i], L[i], R[i]);
		else {
			C[i] = trim(T[i], B[i], L[i], R[i]);
			T[i] = max(T[i], 2);
			L[i] = max(L[i], 2);
			ll bl = get(B[i], L[i]), br = get(B[i], R[i]), tl = get(T[i], L[i]), tr = get(T[i], R[i]);
			vector<ll> v = {bl, br, tl, tr};
			sort(all(v));
			if (v[1] - v[0] > 0) C[i] += RP[v[1] - 1] - (v[0] == 0 ? 0 : RP[v[0] - 1]) - (v[0] == 0 ? 0 : v[0] * getP(v[0], v[1] - 1));
			C[i] += getP(v[1], v[2]) * min(B[i] - T[i] + 1, R[i] - L[i] + 1);
			if (v[3] - v[2] > 0) C[i] += DP[v[2] + 1] - (v[3] == cnt - 1 ? 0 : DP[v[3] + 1]) - (v[3] == cnt - 1 ? 0 : (cnt - 1 - v[3]) * getS(v[2] + 1, v[3]));
		}
	}
    return C;
}

• 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