제출 #1132428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132428		alterio	모자이크 (IOI24_mosaic)	C++20	0 / 100	71 ms	30152 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];

// x - vertical, y - horizontal
ll get(int x, int y) {
	if (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];
}

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];
		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];
		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];
		}
	}
	for (int i = 0; i < q; i++) {
		C[i] = get(T[i], R[i]) - get(T[i], L[i] - 1);
	}
    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