제출 #1132437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132437		alterio	모자이크 (IOI24_mosaic)	C++20	0 / 100	73 ms	30156 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[2 * 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