Submission #1203450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203450		tamyte	Mosaic (IOI24_mosaic)	C++20	100 / 100	139 ms	70908 KiB

mosaic

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

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 = (int)X.size();
	int Q = (int)T.size();
	vector<ll> C(Q);
	if (N <= 5) {
		vector<vector<int>> dp(N, vector<int>(N));
		for (int i = 0; i < N; ++i) {
			dp[i][0] = Y[i];
			dp[0][i] = X[i];
		}
		for (int i = 1; i < N; ++i) {
			for (int j = 1; j < N; ++j) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] == 0);
			}
		}
		for (int i = 0; i < Q; ++i) {
			for (int j = T[i]; j <= B[i]; ++j) {
				for (int k = L[i]; k <= R[i]; ++k) {
					C[i] += dp[j][k];
				}
			}
		}
		return C;
	}
	vector<vector<ll>> dpx(6, vector<ll>(N + 1)), dpy(N + 1, vector<ll>(6)), psx(6, vector<ll>(N + 1)), psy(N + 1, vector<ll>(6));
	for (int i = 0; i < N; ++i) {
		dpx[1][i + 1] = X[i];
		dpy[i + 1][1] = Y[i];
		if (i < 5) {
			dpx[i + 1][1] = Y[i];
			dpy[1][i + 1] = X[i];
		}
	}
	for (int i = 2; i <= 5; ++i) {
		for (int j = 2; j <= N; ++j) {
			dpx[i][j] = (dpx[i - 1][j] + dpx[i][j - 1] == 0);
			dpy[j][i] = (dpy[j - 1][i] + dpy[j][i - 1] == 0);
		}
	}
	for (int i = 1; i <= 5; ++i) {
		for (int j = 1; j <= N; ++j) {
			psx[i][j] = psx[i - 1][j] + psx[i][j - 1] - psx[i - 1][j - 1] + dpx[i][j];
		}
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= 5; ++j) {
			psy[i][j] = psy[i - 1][j] + psy[i][j - 1] - psy[i - 1][j - 1] + dpy[i][j];
		}
	}
	for (int i = 0; i < Q; ++i) {T[i]++; B[i]++; L[i]++; R[i]++;}
	vector<ll> px1(N + 1), py1(N + 1), px2(N + 1), py2(N + 1);
	for (int i = 5; i <= N; ++i) {
		px1[i] = px1[i - 1] + dpx[5][i];
		py1[i] = py1[i - 1] + dpy[i][5];
		px2[i] = px2[i - 1] + px1[i];
		py2[i] = py2[i - 1] + py1[i];
	}
	auto sum = [&](int x, int y) -> ll {
		if (x < 0 || y < 0) return 0;
		if (x <= 5) return psx[x][y];
		if (y <= 5) return psy[x][y];
		ll res = psx[4][y] + psy[x][4] - psx[4][4];
		int excl = min(x - 4, y - 4);
		res -= 1LL * excl * dpx[5][5];
		res += px2[y] - px2[y - excl];
		res += py2[x] - py2[x - excl];
		return res;
	};
	for (int i = 0; i < Q; ++i) {
		C[i] = sum(B[i], R[i]) - sum(T[i] - 1, R[i]) - sum(B[i], L[i] - 1) + sum(T[i] - 1, L[i] - 1);
	}
	return C;;
}


/*
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: 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