Submission #986404

#	Time	Username	Problem	Language	Result	Execution time	Memory
986404		Pyqe	Rectangles (IOI19_rect)	C++17	100 / 100	3442 ms	220216 KiB

rect

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,m,nm=0,nn[2],a[2501][2501],dsu[2][2501],ls[2501],vl[2501][2501],fq[2501];
pair<int,int> as[2501];
pair<pair<int,int>,int> ass[6250001],dp[2][2501];

inline int val(int xx,int y,int x)
{
	if(!xx)
	{
		swap(y,x);
	}
	return a[y][x];
}

int fd(int xx,int x)
{
	if(dsu[xx][x]!=x)
	{
		dsu[xx][x]=fd(xx,dsu[xx][x]);
	}
	return dsu[xx][x];
}

long long count_rectangles(vector<vector<int>> aa)
{
	int rr,i,j,r,r2,ii,u,k,l,w,cr,tg,pp,kk,p,tmp[2501],c,z=0;
	
	n=aa.size();
	m=aa[0].size();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a[i][j]=aa[i-1][j-1];
		}
	}
	for(rr=0;rr<2;rr++)
	{
		swap(n,m);
		if(rr)
		{
			sort(ass+1,ass+nm+1);
			pp=1;
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				as[j]={val(rr,i,j),j};
				for(ii=0;ii<2;ii++)
				{
					dsu[ii][j]=j;
				}
				ls[j]=0;
				if(rr)
				{
					fq[j]=0;
				}
			}
			sort(as+1,as+m+1);
			for(;pp<=nm&&ass[pp].fr.fr<=i;pp++)
			{
				k=ass[pp].sc;
				w=ass[pp].fr.sc;
				fq[k]++;
				vl[k][fq[k]]=w;
			}
			l=0;
			for(j=1;j<=m;j++)
			{
				k=as[j].sc;
				w=as[j].fr;
				for(u=-1;u<=1;u+=2)
				{
					if(k+u&&k+u<=m&&val(rr,i,k+u)<=val(rr,i,k))
					{
						if(rr)
						{
							cr=fd(0,k);
							tg=fd(0,k+u);
							c=0;
							for(r=1;r<=fq[cr];r++)
							{
								kk=vl[cr][r];
								p=lower_bound(vl[tg]+1,vl[tg]+fq[tg]+1,kk)-vl[tg];
								if(p<=fq[tg]&&vl[tg][p]==kk)
								{
									c++;
									tmp[c]=kk;
								}
							}
						}
						for(ii=0;ii<2;ii++)
						{
							dsu[ii][fd(ii,k-ii+(u+1)/2)]=fd(ii,k-1+ii+(u+1)/2);
						}
						if(rr)
						{
							cr=fd(0,k);
							fq[cr]=c;
							for(r=1;r<=c;r++)
							{
								vl[cr][r]=tmp[r];
							}
						}
					}
				}
				if(j==m||w!=as[j+1].fr)
				{
					for(r=l+1;r<=j;r++)
					{
						k=as[r].sc;
						cr=fd(0,k);
						tg=fd(1,k);
						if(ls[cr]<j)
						{
							ls[cr]=j;
							if(!rr)
							{
								nm++;
								ass[nm]={{tg,cr},i};
							}
							else
							{
								p=lower_bound(dp[0]+1,dp[0]+nn[0]+1,mp(mp(cr,tg),0))-dp[0];
								w=1;
								if(p<=nn[0]&&dp[0][p].fr.fr==cr&&dp[0][p].fr.sc==tg)
								{
									w+=dp[0][p].sc;
								}
								nn[1]++;
								dp[1][nn[1]]={{cr,tg},w};
								for(r2=1;r2<=fq[cr];r2++)
								{
									kk=vl[cr][r2];
									z+=i-kk+1<=w&&kk>1&&cr>1&&i<n&&tg<m;
								}
							}
						}
					}
					l=j;
				}
			}
			if(rr)
			{
				nn[0]=nn[1];
				for(j=1;j<=nn[0];j++)
				{
					dp[0][j]=dp[1][j];
				}
				sort(dp[0]+1,dp[0]+nn[0]+1);
				nn[1]=0;
			}
		}
	}
	return z;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:111:18: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         vl[cr][r]=tmp[r];
      |         ~~~~~~~~~^~~~~~~
rect.cpp:34:35: warning: 'pp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |  int rr,i,j,r,r2,ii,u,k,l,w,cr,tg,pp,kk,p,tmp[2501],c,z=0;
      |                                   ^~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28