前50pts求助
查看原帖
前50pts求助
148507
_Imaginary_楼主2022/5/2 11:06

RT,WA了4个点,只过了一个点。

namespace k_is_not_1{
	const int N=205,K=1005;
	int n=0;
	int sum[N][N][K];
	int num[N][N][K];
	int a[N][N];
	void read()
	{
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
				scanf("%d",&a[i][j]);
				n=max(n,a[i][j]);
			}
	}
	void init()
	{
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
				for(int k=0;k<=n;k++)
				{
					sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(a[i][j]>=k?a[i][j]:0);
					num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(a[i][j]>=k?1:0);
				}
	}
	int query_sum(int x1,int y1,int x2,int y2,int k) {return sum[x2][y2][k]-sum[x1-1][y2][k]-sum[x2][y1-1][k]+sum[x1-1][y1-1][k];}
	int query_num(int x1,int y1,int x2,int y2,int k) {return num[x2][y2][k]-num[x1-1][y2][k]-num[x2][y1-1][k]+num[x1-1][y1-1][k];}
	int solve_query(int x1,int y1,int x2,int y2,ll h)
	{
		int L=0,R=n,mid;
		while(L<=R)
		{
			mid=(L+R)>>1;
			if(query_sum(x1,y1,x2,y2,mid)>h) L=mid+1;
			else R=mid-1;
		}
//		printf("R=%d\n",R);
		mid=R;
		int ans,qaq;
		if(R==-1) 
		{
			if(query_sum(x1,y1,x2,y2,0)<h) return -1;
			ans=query_num(x1,y1,x2,y2,0);
		}
		else
		{
			qaq=h-query_sum(x1,y1,x2,y2,mid+1);
			ans=query_num(x1,y1,x2,y2,R+1)+(qaq-1)/mid+1;	
		}
		return ans>(y2-y1+1)*(x2-x1+1)?-1:ans;
	}
	void solve()
	{
		read();
		init();
		while(m--)
		{
			int ta,tb,tc,td;
			int te,tf;
			scanf("%d%d%d%d%d",&ta,&tb,&tc,&td,&te);
			tf=solve_query(ta,tb,tc,td,te);
			if(tf==-1) printf("Poor QLW\n");
			else printf("%d\n",tf);
		}
	}
}
2022/5/2 11:06
加载中...