Submission #1245343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245343		dpsaveslives	Mosaic (IOI24_mosaic)	C++20	100 / 100	107 ms	35656 KiB

mosaic

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


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

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

int A[2*N];
int pr1[2*N];
int sf1[2*N];
ll pr2[2*N];
ll sf2[2*N];


// N is the middle (N+i, N-i)

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+1; 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=0; i<=n; i++) A[N+i] = horz[K+1][K+1+i], A[N-i] = vert[K+1+i][K+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];
		}
	}
	for (int i=1; i<2*N; i++) pr1[i] = pr1[i-1] + A[i];
	for (int i=2*N-2; i>=0; i--) sf1[i] = sf1[i+1] + A[i];
	for (int i=1; i<2*N; i++) pr2[i] = pr2[i-1] + pr1[i];
	for (int i=2*N-2; i>=0; i--) sf2[i] = sf2[i+1] + sf1[i];

	vector<ll> 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
		if (t<=K) res[q] += prh[pt][r] - prh[t-1][r] - prh[pt][l-1] + prh[t-1][l-1];
		if (t<=K) t = pt+1;
		if (t > b) continue;
		int pl = min(r, K);
		// add t b l pl
		if (l<=K) res[q] += prv[b][pl] - prv[t-1][pl] - prv[b][l-1] + prv[t-1][l-1];
		if (l<=K) l = pl + 1;
		if (l > r) continue;
		ll wsz = (ll)min(r - l + 1, b - t + 1);
		int id1, id2;
		// t b l r
		int s = min(b, l); b-=s; l-=s;
		if (b) id1 = N-b; else id1 = N+l;
		s = min(t,r); t-=s; r-=s;
		if (t) id2 = N - t; else id2 = N + r;
		int j1 = id1 + wsz - 1;
		int j2 = id2 - wsz + 1;
		res[q] += wsz * (pr1[j2] - pr1[j1-1]);
		j1--; j2++; if (j1 < id1 || j2 > id2) continue;
		// id1 .. j1
		// (id1) 1, 2, 3 ... - (j1+1) 1, 2, 3, ... - sf[j1+1] * (j1-id1+1))
		res[q] += sf2[id1] - sf2[j1+1] - sf1[j1+1] * (ll)(j1-id1+1);
		res[q] += pr2[id2] - pr2[j2-1] - pr1[j2-1] * (ll)(id2-j2+1);

	}
	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