CF1740G Dangerous Laser Power

题面传送门

不是很理解为啥场上只有很少的人过掉这道题。

首先看看这种题目不让你输出最大值而且SPJ还死难写的就猜它全部可以取到并且最优解唯一。

然后你翻了翻CF提交记录发现它是全文比较的。

因为这个过程在chkmax，所以考虑从小到大加入点并且判定点的类型。

考虑最小的点，可以发现除了它四周射入的，其余都是不会影响到它的，因此它是直行的。

然后这个最小的点删掉以后，它上下和左右相当于直接联通了。因此可以用链表维护这个东西。而它两边者射入的激光相当于直接射到了四周，也可以用链表维护。

然后直接模拟这个过程即可，时间复杂度\(O(n^2\log n)\)

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e3+5,M=1e6+5,K=(1<<10)+5,mod=998244353,Mod=mod-1;ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,A[M],P[M*8],Ans[M],Op[M*4][2],Ts,To,B[M];bool cmp(int x,int y){return A[x]<A[y];}
int Id(int k,int x,int y){if(x<0||x>=n||y<0||y>=m) return -1;return k*n*m+x*m+y;}
int main(){
	freopen("1.in","r",stdin);
	int i,j,h;scanf("%d%d",&n,&m);k=n*m;for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&A[Id(0,i,j)]),B[Id(0,i,j)]=Id(0,i,j);sort(B,B+k,cmp);
	for(i=0;i<n;i++) for(j=0;j<m;j++) P[Id(0,i,j)]=P[Id(4,i,j)]=Id(2,i-1,j),P[Id(1,i,j)]=P[Id(5,i,j)]=Id(3,i,j+1),P[Id(2,i,j)]=P[Id(6,i,j)]=Id(0,i+1,j),P[Id(3,i,j)]=P[Id(7,i,j)]=Id(1,i,j-1);
	for(i=0;i<n;i++) for(j=0;j<m;j++) for(h=0;h<4;h++) Op[Id(h,i,j)][1]=1;
	for(j=0;j<k;j++){
		int p=B[j];Ts=0;for(i=0;i<4;i++) Ts+=Op[p+i*k][(A[p]&1)^1];Ans[p]=(Ts&=1);
		for(i=0;i<4;i++){
			To=(i+2+Ts)&3; ~P[To*k+p]&&(Op[P[To*k+p]][A[p]&1]+=Op[p+i*k][0]+Op[p+i*k][1]);
			~P[p+(i+4)*k]&&(P[P[p+(i+4)*k]]=P[To*k+p]);
			~P[p+To*k]&&(P[P[p+To*k]+4*k]=P[p+(i+4)*k]); 
		}
	}for(i=0;i<n;Pc('\n'),i++) for(j=0;j<m;j++) printf("%d",Ans[Id(0,i,j)]);
}