C++14(g++5.4) 解法, 执行用时: 316ms, 内存消耗: 196388K, 提交时间: 2020-10-07 17:01:50

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 10010
int n,w,h,m,l[N],r[N],cnt[N],c[5010][N];
LL sx[N],sy[N];
bool check(LL i,LL sx,LL sy,LL cnt)
{
	if(!cnt)return true;
	if(i&1){
		//check x
		return 2ll*(l[i]-1)*cnt<sx && sx<2ll*r[i]*cnt;
	}
	else{
		return 2ll*(l[i]-1)*cnt<sy && sy<2ll*r[i]*cnt;
	}
}
int main()
{
	scanf("%d%d",&n,&w);
	scanf("%d%d",&h,&m);
	for(int i=1;i<=h;i++){
		for(int j=1;j<=n;j++)
			c[i][j]=1,sx[i]+=i&1?2*j-1:n,sy[i]+=i&1?n:2*j-1;
		l[i]=1,r[i]=n;
		cnt[i]=n;
	}
	for(int o=1;o<=m;o++){
		int st,k;
		scanf("%d%d",&st,&k);
		c[st][k]=0;
		sx[st]-=st&1?2*k-1:n;
		sy[st]-=st&1?n:2*k-1;
		cnt[st]--;
		while(!c[st][l[st]] && l[st]<=n)l[st]++;
		while(!c[st][r[st]] && r[st]>=1)r[st]--;
		if(cnt[st]==0){
			if(st==h)h--;
			else return printf("yes\n%d\n",o),0;
		}
		//if(r[st]<l[st])return printf("yes\n%d\n",o),0;
		LL SX=0,SY=0,tot=0;
		for(int i=h;i>1;i--){
			SX+=sx[i];
			SY+=sy[i];
			tot+=cnt[i];
			//x=SX/tot,y=SY/tot
			//
			if(!check(i-1,SX,SY,tot))
				return printf("yes\n%d\n",o),0;
		}
	}
	return printf("no\n"),0;
}

C++11(clang++ 3.9) 解法, 执行用时: 224ms, 内存消耗: 196356K, 提交时间: 2020-10-08 13:19:07

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 10010
int n,w,h,m,l[N],r[N],cnt[N],c[5010][N];
LL sx[N],sy[N];
bool check(LL i,LL sx,LL sy,LL cnt)
{
	if(!cnt)
	return true;
	if(i&1)
	{
		return 2ll*(l[i]-1)*cnt<sx&&sx<2ll*r[i]*cnt;
	}
	else 
	{
		return 2ll*(l[i]-1)*cnt<sy&&sy<2ll*r[i]*cnt;
	}
}
int main()
{
	scanf("%d%d",&n,&w);
	scanf("%d%d",&h,&m);
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=n;j++)
		c[i][j]=1,sx[i]+=i&1?2*j-1:n,sy[i]+=i&1?n:2*j-1;
		l[i]=1,r[i]=n;
		cnt[i]=n;
	}
	for(int o=1;o<=m;o++)
	{
		int st,k;
		scanf("%d%d",&st,&k);
		c[st][k]=0;
		sx[st]-=st&1?2*k-1:n;
		sy[st]-=st&1?n:2*k-1;
		cnt[st]--;
		while(!c[st][l[st]]&&l[st]<=n)
		l[st]++;
		while(!c[st][r[st]]&&r[st]>=1)
		r[st]--;
		if(cnt[st]==0)
		{
			if(st==h)
			h--;
			else return printf("yes\n%d\n",o),0; 
		}
		LL SX=0,SY=0,tot=0;
		for(int i=h;i>1;i--)
		{
			SX+=sx[i];
			SY+=sy[i];
			tot+=cnt[i];
			if(!check(i-1,SX,SY,tot))
			return printf("yes\n%d\n",o),0;
		}
	}
	return printf("no\n"),0;
}