Submission #1233697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233697		vidux	Mosaic (IOI24_mosaic)	C++17	5 / 100	993 ms	2162688 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>
#define fi first
#define se second
#define ALL(x) (x.begin()), (x.end())
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_ARR(x) /*{ cerr << #x << ": "; { for (auto &y : x) cout << y << " "; cout << endl; } }*/
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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 q = SZ(T);
	int n = SZ(X);
	{
		vvl a(n, vl(n));
		for (int i = 0; i < n; i++) a[i][0] = Y[i], a[0][i] = X[i];
		for (int i = 0; i < n-1; i++) for (int j = 0; j < n-1; j++) {
			int k = a[i][j+1] + a[i+1][j];
			a[i+1][j+1] = (k == 0);
		}
		for (int i = 0; i < n; i++) DEBUG_ARR(a[i]);
	}
	vl ans(q);
	vvi rows(3, vi(n)), cols(3, vi(n));
	for (int i = 0; i < n; i++) rows[0][i] = X[i], cols[0][i] = Y[i];
	rows[1][0] = cols[0][1];
	rows[2][0] = cols[0][2];
	cols[1][0] = rows[0][1];
	cols[2][0] = rows[0][2];
	for (int i = 1; i < 3; i++) {
		for (int j = 1; j < n; j++) {
			int k = rows[i-1][j]+rows[i][j-1];
			rows[i][j] = (k == 0);
			k = cols[i-1][j]+cols[i][j-1];
			cols[i][j] = (k == 0);
		}
	} 
	vvi prefr(3, vi(n+1)), prefc(3, vi(n+1));
	for (int i = 0; i < 3; i++) for (int j = 0; j < n; j++) {
		prefr[i][j+1] = prefr[i][j]+rows[i][j];
		prefc[i][j+1] = prefc[i][j]+cols[i][j];
	}
	for (auto r : rows) DEBUG_ARR(r);
	for (auto c : cols) DEBUG_ARR(c);
	vi b;
	for (int i = n-1; i >= 3; i--) b.push_back(cols[2][i]);
	for (int i = 2; i < n; i++) b.push_back(rows[2][i]);
	DEBUG_ARR(b);
	vl prefb(SZ(b)+1);
	for (int i = 0; i < SZ(b); i++) prefb[i+1] = prefb[i]+b[i];
	vl prefli(SZ(b)+1);
	for (int i = 0; i < SZ(b); i++) prefli[i+1] = prefli[i]+b[i]*(i+1);
	vl prefri(SZ(b)+1);
	for (int i = 0; i < SZ(b); i++) prefri[SZ(b)-1-i] = prefri[SZ(b)-i]+b[SZ(b)-1-i]*(i+1);
	DEBUG_ARR(prefli);
	DEBUG_ARR(prefri);
	for (int t = 0; t < q; t++) {
		int xl = L[t], xr = R[t], yt = T[t], yb = B[t];
		if (yb < 3) {
			for (int i = yt; i <= yb; i++) ans[t] += prefr[i][xr+1]-prefr[i][xl];
			continue;
		}
		if (xr < 3) {
			for (int i = xl; i <= xr; i++) ans[t] += prefc[i][yb+1]-prefc[i][yt];
			continue;
		}
		while (xl < 3) {
			ans[t] += prefc[xl][yb+1]-prefc[xl][yt];
			xl++;
		}
		while (yt < 3) {
			ans[t] += prefr[yt][xr+1]-prefr[yt][xl];
			yt++;
		}
		int y = n-1-yt;
		int l = xl+y-2;
		int r = xr+y-2;
		l -= yb-yt;
		int w = xr-xl+1, h = yb-yt+1;
		int mn = min(w, h);
		int lm = l+mn-1;
		int rm = r-mn+1;
		ans[t] += prefli[lm]-prefli[l];
		ans[t] += prefri[rm]-prefri[r];
		ans[t] += (prefb[rm+1]-prefb[lm])*mn;
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22