Submission #1243351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243351		allin27x	Mosaic (IOI24_mosaic)	C++20	12 / 100	448 ms	330764 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
#define int long long


const int N = 2e5+5;
const int K = 50;

int vert[N][K+2];
int horz[K+2][N];
int prv[N][K+2];
int prh[K+2][N];


vector<long long> mosaic(vector<signed> X, vector<signed> Y, vector<signed> T, vector<signed> B, vector<signed> L, vector<signed> R) {
	int n = X.size();
	for (int i=0; i<n; i++) horz[1][i+1] = X[i];
	for (int i=0; i<n; i++) vert[i+1][1] = Y[i];
	for (int i=0; i<min(n, K); i++) horz[i+1][1] = Y[i];
	for (int i=0; i<min(n, K); i++) vert[1][i+1] = X[i];
	for (int i=2; i<=K; i++) {
		for (int j=2; j<=n; j++) {
			vert[j][i] = !vert[j-1][i] && !vert[j][i-1];
			horz[i][j] = !horz[i-1][j] && !horz[i][j-1];
		}
	}
	for (int i=1; i<=K; i++) {
		for (int j=1; j<=n; j++) {
			prv[j][i] = prv[j-1][i] + prv[j][i-1] - prv[j-1][i-1] + vert[j][i];
			prh[i][j] = prh[i-1][j] + prh[i][j-1] - prh[i-1][j-1] + horz[i][j];
		}
	}
	vector<int> res((int)T.size(), 0);
	for (int q=0; q<T.size(); q++) {
		int t = T[q]+1; int b=B[q]+1; int l=L[q]+1; int r=R[q]+1;
		int pt = min(b, K);
		// add t pt l r
		res[q] += prh[pt][r] - prh[t-1][r] - prh[pt][l-1] + prh[t-1][l-1];
		t = pt+1;
		if (t > b) continue;
		int pl = min(r, K);
		// add t b l pl
		res[q] += prv[b][pl] - prv[t-1][pl] - prv[b][l-1] + prv[t-1][l-1];
		l = pl + 1;
		if (l > r) continue;
	}
	return res;
}


//
// #undef int
// #include <cassert>
// #include <cstdio>
// #include <vector>
//
// int main() {
// 	int N;
// 	assert(1 == scanf("%d", &N));
// 	std::vector<int> X(N), Y(N);
// 	for (int i = 0; i < N; i++)
// 		assert(1 == scanf("%d", &X[i]));
// 	for (int i = 0; i < N; i++)
// 		assert(1 == scanf("%d", &Y[i]));
// 	int Q;
// 	assert(1 == scanf("%d", &Q));
// 	std::vector<int> T(Q), B(Q), L(Q), R(Q);
// 	for (int k = 0; k < Q; k++)
// 		assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
// 	fclose(stdin);
//
// 	std::vector<long long> C = mosaic(X, Y, T, B, L, R);
//
// 	int S = (int)C.size();
// 	for (int k = 0; k < S; k++)
// 		printf("%lld\n", C[k]);
// 	fclose(stdout);
//
// 	return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22