Submission #1124228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124228		Mousa_Aboubaker	Mosaic (IOI24_mosaic)	C++20	22 / 100	279 ms	207632 KiB

mosaic

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

vector<long long> mosaic(vector<int> X, vector<int> Y,
                        vector<int> T, vector<int> B,
                        vector<int> L, vector<int> R)
{
	vector<int> x = X, y = Y, t = T, b = B, l = L, r = R;
	int n = (int)x.size(), q = (int)t.size();
	if(n <= 5000)
	{
		vector a(n, vector<int>(n));
		for(int i = 0; i < n; i++)
		{
			a[0][i] = x[i];
			a[i][0] = y[i];
		}
		for(int i = 1; i < n; i++)
			for(int j = 1; j < n; j++)
				a[i][j] = a[i - 1][j] == 0 and a[i][j - 1] == 0;
		vector pref(n + 1, vector<int>(n + 1));
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + a[i][j];
			}
		}

		vector<long long> res(q);
		for(int i = 0; i < q; i++)
		{
			int i1 = t[i], j1 = l[i];
			int i2 = b[i], j2 = r[i];
			res[i] = pref[i2 + 1][j2 + 1] - pref[i1][j2 + 1] - pref[i2 + 1][j1] + pref[i1][j1];
		}

		return res;
	}

	vector<int> x2(n - 1), y2(n - 1);
	x2[0] = x[1] == 0 and y[1] == 0;
	for(int i = 2; i < n; i++)
	{
		x2[i - 1] = x[i] == 0 and x2[i - 2] == 0;
	}
	y2[0] = x2[0];
	for(int i = 2; i < n; i++)
	{
		y2[i - 1] = y[i] == 0 and y2[i - 2] == 0;
	}
	vector<int> x3(n - 2), y3(n - 2);
	x3[0] = x2[1] == 0 and y2[1] == 0;
	for(int i = 2; i < n - 1; i++)
	{
		x3[i - 1] = x2[i] == 0 and x3[i - 2] == 0;
	}
	y3[0] = x2[1] == 0 and y2[1] == 0;
	for(int i = 2; i < n - 1; i++)
	{
		y3[i - 1] = y2[i] == 0 and y2[i - 2] == 0;
	}

	vector<long long> res(q);
	for(int i = 0; i < q; i++)
	{
		int i1 = t[i], i2 = b[i];
		int j1 = l[i], j2 = r[i];
		if(i1 == 0)
		{
			res[i] = x[j1];
			continue;
		}
		if(j1 == 0)
		{
			res[i] = y[i1];
			continue;
		}
		if(i1 == 1)
		{
			res[i] = x2[j1 - 1];
			continue;
		}
		if(j1 == 1)
		{
			res[i] = y2[i1 - 1];
			continue;
		}
		if(i1 < j1)
			res[i] = x3[j1 - i1 + 1];
		else
			res[i] = y3[i1 - j1 + 1];
	}

	return res;
}

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