Submission #1232706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232706		MuhammadSaram	Mosaic (IOI24_mosaic)	C++20	100 / 100	643 ms	48508 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()

vector<long long> mosaic(vector<int> a, vector<int> b,vector<int> r,
							vector<int> r1,vector<int> c, vector<int> c1)
{
	int n=a.size();
	vector<int> rw[3],cl[3];
	vector<ll> v;
	set<pair<int,int>> se;
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
		{
			if (i>3 && j>3) break;
			if (!i)
			{
				if (a[j]) se.insert({i,j}),rw[0].push_back(j);
			}
			else if (!j)
			{
				if (b[i])
				{
					se.insert({i,j}),cl[0].push_back(i);
					if (i<3) rw[i].push_back(j);
				}
			}
			else
			{
				if (!se.count({i-1,j}) && !se.count({i,j-1}))
				{
					se.insert({i,j});
					if (min(i,j)==3)
						v.push_back(i-j);
					else
					{
						if (i<3) rw[i].push_back(j);
						else if (j<3) cl[j].push_back(i);
					}
				}
			}
		}
	for (int i=0;i<3;i++)
		sort(all(rw[i])),sort(all(cl[i]));
	sort(all(v));
	int m=v.size();
	ll pre[m]={};
	for (int i=1;i<=m;i++)
		pre[i]=pre[i-1]+v[i-1];
	vector<ll> ans(r.size());
	for (int i=0;i<(int)r.size();i++)
	{
		for (int j=0;j<3;j++)
		{
			if (j>=r[i] && j<=r1[i])
				ans[i]+=upper_bound(all(rw[j]),c1[i])-lower_bound(all(rw[j]),c[i]);
			if (j>=c[i] && j<=c1[i] && r1[i]>2)
				ans[i]+=upper_bound(all(cl[j]),r1[i])-lower_bound(all(cl[j]),max(3,r[i]));
		}
		r[i]=max(r[i],3);
		c[i]=max(c[i],3);
		if (r[i]>r1[i] or c[i]>c1[i]) continue;
		if (lower_bound(all(v),r[i]-c[i])!=upper_bound(all(v),r1[i]-c[i]))
		{
			int x=lower_bound(all(v),r[i]-c[i])-begin(v);
			int y=upper_bound(all(v),r1[i]-c[i])-begin(v)-1;
			int s=x-1,e=y+1;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (r1[i]-(v[mid]+c[i])>=c1[i]-c[i])
					s=mid;
				else
					e=mid;
			}
			ans[i]+=1ll*(c1[i]-c[i]+1)*(s-x+1);
			ll su=pre[y+1]-pre[s+1]+1ll*c[i]*(y-s);
			ans[i]+=1ll*(r1[i]+1)*(y-s)-su;
		}
		if (c[i]==c1[i]) continue;
		c[i]++;
		if (lower_bound(all(v),r[i]-c1[i])!=upper_bound(all(v),r[i]-c[i]))
		{
			int x=lower_bound(all(v),r[i]-c1[i])-begin(v);
			int y=upper_bound(all(v),r[i]-c[i])-begin(v)-1;
			int s=x-1,e=y+1;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (c1[i]-(r[i]-v[mid])>=r1[i]-r[i])
					e=mid;
				else
					s=mid;
			}
			ans[i]+=1ll*(r1[i]-r[i]+1)*(y-e+1);
			ll su=1ll*r[i]*(e-x)-(pre[e]-pre[x]);
			ans[i]+=1ll*(c1[i]+1)*(e-x)-su;
		}
	}
	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