Submission #1101136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101136		rainboy	Mosaic (IOI24_mosaic)	C++17	100 / 100	133 ms	31680 KiB

mosaic

#include "mosaic.h"
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;

const int N = 200000;

int dp[3][N], dq[N][3];
int ss[3][N], tt[N][3];
int uu[N * 2]; long long vv[N * 2];
int n;

int sum(int l, int r) {
	return l > r ? 0 : uu[r] - (l == 0 ? 0 : uu[l - 1]);
}

long long sum_incr(int l, int r) {
	return l > r ? 0 : vv[r] - (l == 0 ? 0 : vv[l - 1]) - (long long) sum(l, r) * (l - 1);
}

long long sum_decr(int l, int r) {
	return l > r ? 0 : (long long) sum(l, r) * (r - l + 2) - sum_incr(l, r);
}

long long solve(int i, int j) {
	if (i < 0 || j < 0)
		return 0;
	if (i < 3)
		return ss[i][j];
	if (j < 3)
		return tt[i][j];
	long long ans = ss[2][j] + tt[i][2] - ss[2][2];
	if (i < j)
		ans += sum_incr(n - 1 + 3 - i, n - 2) + (long long) sum(n - 1, n - 1 + j - i) * (i - 2) + sum_decr(n + j - i, n - 1 + j - 3);
	else
		ans += sum_incr(n - 1 + 3 - i, n - 2 + j - i) + (long long) sum(n - 1 + j - i, n - 1) * (j - 2) + sum_decr(n, n - 1 + j - 3);
	return ans;
}

vl mosaic(vi xx, vi yy, vi iil, vi iir, vi jjl, vi jjr) {
  n = xx.size(); int q = iil.size();
	if (n < 4) {
		xx.resize(4), yy.resize(4);
		for (int i = n; i < 4; i++)
			xx[i] = yy[i] = 0;
		n = 4;
	}
  vl ans(q, 0);
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < n; j++)
			if (i == 0)
				dp[i][j] = xx[j];
			else if (j == 0)
				dp[i][j] = yy[i];
			else
				dp[i][j] = !dp[i - 1][j] && !dp[i][j - 1];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			if (i == 0)
				dq[i][j] = xx[j];
			else if (j == 0)
				dq[i][j] = yy[i];
			else
				dq[i][j] = !dq[i - 1][j] && !dq[i][j - 1];
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < n; j++)
			ss[i][j] = dp[i][j];
	for (int i = 0; i < 3; i++)
		for (int j = 1; j < n; j++)
			ss[i][j] += ss[i][j - 1];
	for (int i = 1; i < 3; i++)
		for (int j = 0; j < n; j++)
			ss[i][j] += ss[i - 1][j];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			tt[i][j] = dq[i][j];
	for (int i = 0; i < n; i++)
		for (int j = 1; j < 3; j++)
			tt[i][j] += tt[i][j - 1];
	for (int i = 1; i < n; i++)
		for (int j = 0; j < 3; j++)
			tt[i][j] += tt[i - 1][j];
	for (int i = 2, j = 2; i < n; i++) {
		uu[n - 1 + j - i] = dq[i][j];
		vv[n - 1 + j - i] = (long long) dq[i][j] * (n - 1 + j - i);
	}
	for (int i = 2, j = 2; j < n; j++) {
		uu[n - 1 + j - i] = dp[i][j];
		vv[n - 1 + j - i] = (long long) dp[i][j] * (n - 1 + j - i);
	}
	for (int d = 1; d < n * 2; d++)
		uu[d] += uu[d - 1];
	for (int d = 1; d < n * 2; d++)
		vv[d] += vv[d - 1];
	for (int h = 0; h < q; h++) {
		int il = iil[h], jl = jjl[h], ir = iir[h], jr = jjr[h];
		ans[h] = solve(ir, jr) - solve(ir, jl - 1) - solve(il - 1, jr) + solve(il - 1, jl - 1);
	}
	return ans;
}

• 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