Submission #1132445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132445		alterio	Mosaic (IOI24_mosaic)	C++20	0 / 100	86 ms	23880 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];

// 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}];
}

pair<ll, int> trim(int x, int y) {
	if (y < 0) return {0, -1};
	ll res = 0;
	for (int i = y; i < 2; i++) {
		res += Y[x][i];
	}
	return {res, max(y, 2)};
}

ll get(int x, int y) {
	if (y < 0 || x < 0) return 0;
	if (x <= 2) return prfX[x][y];
	ll ind = 0;
	if (x < y) ind = f(2, y - (x - 2));
	else ind = f(x - (y - 2), 2);
	return prf[ind];
}

ll special(int x, int y1, int y2) {
	ll ans = 0;
	for (int i = y1; i <= y2; i++) ans += Y[x][i];
	return ans;
}

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] = prfX[j - 1][i] + Y[j][i];
	// 	}
	// }
	// int cnt = 0;
	// for (int i = n - 1; i >= 2; i--) {
	// 	prf[cnt] = (cnt > 0 ? prf[cnt - 1] : 0) + Y[i][2];
	// 	comp[{i, 2}] = cnt++;
	// }
	// for (int i = 3; i < n; i++) {
	// 	prf[cnt] = prf[cnt - 1] + X[2][i];
	// 	comp[{2, i}] = cnt++;
	// }
	// for (int i = 0; i < q; i++) {
	// 	if (R[i] <= 2) C[i] = special(T[i], L[i], R[i]);
	// 	else C[i] = trim(T[i], L[i]).first + get(T[i], R[i]) - get(T[i], trim(T[i], L[i]).second) + getSQ(T[i], L[i]);
	// }
    return C;
}

• 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