Submission #1206376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206376		vidux	Mosaic (IOI24_mosaic)	C++17	53 / 100	95 ms	28336 KiB

mosaic

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

//#define LOCAL

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int INF = 1e9;
const ll LLINF = 1e18;

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);
	vl ans(q);
	if (n < 10) {
		vvl a(n, vl(n));
		FOR(i, n) a[i][0] = Y[i], a[0][i] = X[i];
		FOR(i, n-1) FOR(j, n-1) {
			int k = a[i][j+1] + a[i+1][j];
			a[i+1][j+1] = (k == 0);
		}
		//FORR(r, a) { FORR(x, r) cout << x << " "; cout << endl; } cout << "-------\n";
		vvl pref(n+1, vl(n+1));
		FOR(i, n) FOR(j, n) pref[i+1][j+1] = pref[i+1][j] + pref[i][j+1] - pref[i][j] + a[i][j];
		//FORR(r, pref) { FORR(x, r) cout << x << " "; cout << endl; }
		FOR(t, q) {
			ll sum = pref[B[t]+1][R[t]+1] - pref[T[t]][R[t]+1] - pref[B[t]+1][L[t]] + pref[T[t]][L[t]];
			//cout << sum << endl;
			ans[t] = sum;
		}
		return ans;
		//FORR(x, ans) cout << " > " << x << endl;
		//ans = vl(q);
	}
	/* task 3
	   vl pref(n+1);
	   FOR(i, n) pref[i+1] = pref[i] + X[i];
	FOR(t, q) ans[t] = pref[R[t]+1] - pref[L[t]];
	*/
	/* task 5
	FOR(t, q) {
		if ((L[t] == 0 && R[t] == 0) || (T[t] == 0 && B[t] == 0)) {
			ans[t] = 0;
			continue;
		}
		L[t] = max(L[t], 1);
		T[t] = max(T[t], 1);
		ll h = B[t]-T[t]+1;
		ll w = R[t]-L[t]+1;
		if (h%2 == 0) ans[t] = w*h/2;
		else {
			ll col1, col2;
			col1 = (h+1)/2, col2 = h/2;
			if ((L[t]+T[t]) % 2 == 1) swap(col1, col2);
			ans[t] = col1 * ((w+1)/2) + col2 * (w/2);
			//cout << h << " x " << w << endl;
			//cout << col1 << " " << col2 << endl;
			//cout << (w+1)/2 << " " << w/2 << endl;
			//cout << col1*((w+1)/2) << " " << col2*w/2 << endl;
		}
	}
	*/
	vvi rows(3, vi(n)), cols(3, vi(n));
	FOR(i, n) 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];
	REP(i, 1, 2) {
		REP(j, 1, n-1) {
			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);
		}
	} 
	//FORR(r, rows) { FORR(c, r) cout << c << " "; cout << endl; }
	//FORR(r, cols) { FORR(c, r) cout << c << " "; cout << endl; }
	vi b;
	REPR(i, n-1, 3) b.push_back(cols[2][i]);
	REP(i, 2, n-1) b.push_back(rows[2][i]);
	vl prefb(SZ(b)+1);
	FOR(i, SZ(b)) prefb[i+1] = prefb[i] + b[i];
	//FORR(x, b) cout << x << " "; cout << endl;
	vvl pref(3, vl(n+1));
	FOR(j, 3) FOR(i, n) pref[j][i+1] = pref[j][i] + rows[j][i];
	FOR(t, q) {
		if (T[t] < 3) {
			ans[t] = pref[T[t]][R[t]+1] - pref[T[t]][L[t]];
			continue;
		}
		if (R[t] < 3) {
			REP(i, L[t], R[t]) ans[t] += cols[i][T[t]];
			continue;
		}
		while (L[t] < 3) {
			ans[t] += cols[L[t]][T[t]];
			L[t]++;
		}
		int xl = L[t], xr = R[t], y = n-1-T[t];
		int l = xl+y-2;
		int r = xr+y-2;
		//cout << ">>" << l << endl;
		ans[t] += prefb[r+1] - prefb[l];
	}
	return ans;
}

#ifdef LOCAL
int main() {
	int n; cin >> n;
	vi x(n), y(n);
	FOR(i, n) cin >> x[i];
	FOR(i, n) cin >> y[i];
	int q; cin >> q;
	vi t(q), b(q), l(q), r(q);
	FOR(i, q) cin >> t[i] >> b[i] >> l[i] >> r[i];
	vl ans = mosaic(x, y, t, b, l, r);
	//vl ans = mosaic({0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
	//				{0, 0, 0},
	//				{1, 2, 3}, 
	//				{0, 0, 0}, 
	//				{1, 2, 4});
	FORR(x, ans) cout << x << endl;

    return 0;
}
#endif

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