Submission #1128136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128136		PenguinsAreCute	Mosaic (IOI24_mosaic)	C++20	100 / 100	133 ms	20796 KiB

mosaic

// this is the second time this year mosaic has caused me pain
#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
	int N = X.size();
	while(N<3) {
		X.push_back(0);
		Y.push_back(0);
		N++;
	}
	int gr[N][3], gr2[3][N];
	for(int i=0;i<N;i++) gr[i][0]=Y[i];
	for(int i=0;i<3;i++) gr[0][i]=X[i];
	for(int i=0;i<3;i++) gr2[i][0]=Y[i];
	for(int i=0;i<N;i++) gr2[0][i]=X[i];
	for(int i=1;i<N;i++) for(int j=1;j<3;j++) gr[i][j]=!(gr[i-1][j]||gr[i][j-1]);
	for(int i=1;i<3;i++) for(int j=1;j<N;j++) gr2[i][j]=!(gr2[i-1][j]||gr2[i][j-1]);
	vector<int> arr(2*N-4,0);
	vector<long long> arr2(2*N-4);
	auto trapezium = [&arr, &arr2](int a, int b, int c, int d) {
		long long ans = arr2[b] - arr2[a-1] - (a - 1LL) * (arr[b] - arr[a-1]);
		ans += (arr[c-1] - arr[b]) * (b - a + 1LL);
		ans += arr2[c-1] - arr2[d] + (d + 1LL) * (arr[d] - arr[c-1]);
		return ans;
		// part 1: a to b
		// part 2: b+1 to c-1
		// part 3: c to d
		// (d+1-x) (arr[x])
	};
	for(int i=N-1;i>2;i--) arr[N-i]=gr[i][2];
	for(int i=2;i<N;i++) arr[N+i-4]=gr2[2][i];
	for(int i=1;i<2*N-4;i++) {
		arr2[i] = arr2[i-1] + i * arr[i];
		arr[i]+=arr[i-1];
	}
	for(int i=0;i<3;i++) for(int j=1;j<N;j++)
		gr2[i][j]+=gr2[i][j-1];
	for(int i=0;i<3;i++) for(int j=1;j<N;j++)
		gr[j][i]+=gr[j-1][i];
	// (N-1, 2) -> 2-(N-1) = 3 - N -> + (N - 2).
	// (2, N-1) -> N - 3 -> 2N - 3???
	int Q = (int)T.size();
	std::vector<long long> C(Q, 0);
	for(int i=0;i<Q;i++) {
		if(B[i] < 2) {
			for(int j=T[i];j<=B[i];j++)
				C[i] += gr2[j][R[i]]-(L[i]?gr2[j][L[i]-1]:0);
			continue;
		}
		if(R[i] < 2) {
			for(int j=L[i];j<=R[i];j++)
				C[i] += gr[B[i]][j]-(T[i]?gr[T[i]-1][j]:0);
			continue;
		}
		while(L[i] < 2) {
			C[i] += gr[B[i]][L[i]]-(T[i]?gr[T[i]-1][L[i]]:0);
			L[i]++;
		}	
		while(T[i] < 2) {
			C[i] += gr2[T[i]][R[i]]-(L[i]?gr2[T[i]][L[i]-1]:0);
			T[i]++;
		}
		C[i] += trapezium(L[i]-B[i]+(N-2),L[i]-T[i]+(N-2),R[i]-B[i]+(N-2),R[i]-T[i]+(N-2));
		// Start: L - D
		// Mid: L - T
		// Then: R - D
		// Last: R - T
		// L - D to L - T: [x - (L - D) + 1] * 
	}
	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