Submission #1233564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233564		AMnu	Mosaic (IOI24_mosaic)	C++20	100 / 100	117 ms	24648 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e5+5;

int N, Q;
ll A[4][2*MAXN];

int f(int x,int y) {
	return (1-x)*(1-y);
}

ll ans(int T,int B,int L,int R) {
	ll res = 0;
	for (int i=0;i<2;i++) {
		if (T == 0) {
			res += A[i][N+R]-A[i][N+L-1];
			T++;
		}
		if (L == 0) {
			res += A[i][N-T]-A[i][N-B-1];
			L++;
		}
		if (T>B || L>R) return res;
		T--; B--; L--; R--;
	}
	int X = N+L-T, Y = N+R-B, Z = min(R-L,B-T)+1;
	if (X > Y) swap(X,Y);
	res += Z*(A[2][Y]-A[2][X]);
	res += (Y+Z)*(A[2][Y+Z]-A[2][Y]);
	res -= A[3][Y+Z]-A[3][Y];
	res -= (X-Z)*(A[2][X]-A[2][X-Z]);
	res += A[3][X]-A[3][X-Z];
	return res;
}

vector<ll>mosaic(vector<int>X,vector<int>Y,vector<int>T,vector<int>B,vector<int>L,vector<int>R) {
	N = X.size();
	Q = T.size();
	for (int i=0;i<N;i++) {
		A[0][N+i] = X[i];
		A[0][N-i] = Y[i];
	}
	for (int i=1;i<3;i++) {
		A[i][N] = f(A[i-1][N-1],A[i-1][N+1]);
		for (int j=1;j<N;j++) {
			A[i][N+j] = f(A[i-1][N+j+1],A[i][N+j-1]);
			A[i][N-j] = f(A[i-1][N-j-1],A[i][N-j+1]);
		}
	}
	for (int i=1;i<2*N;i++) {
		A[3][i] = A[2][i]*i;
		for (int j=0;j<4;j++) {
			A[j][i] += A[j][i-1];
		}
	}
	vector<ll> res;
	for (int i=0;i<Q;i++) {
		res.push_back(ans(T[i],B[i],L[i],R[i]));
	}
	return res;
}

• 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