yukicoder : No.2520 L1 Explosion

この回は問題数多いけど難易度が手ごろなのでサクサク解けるね。
https://yukicoder.me/problems/no/2520

問題

N体のモンスターがおり、それぞれ2次元座標上の位置と体力が与えられる。

今ある点で攻撃力Mの爆発を起こしたとき、各モンスターにはMから(爆発位置からモンスターの位置のマンハッタン距離)を引いた分だけ体力を減らすことができる。
ちょうどi体のモンスターの体力を0以下にできる爆発位置の面積を求めよ。

解法

45度座標変換すると、各モンスターの体力を0以下にできる範囲は軸に平行な正方形領域となる。
あとは座標圧縮して領域を分割したうえで平面走査していけば、各領域内で体力を0にできるモンスター数を適宜計算できる。

int N;
ll M;
ll X[3030],Y[3030],H[3030];
ll L[3030],R[3030],D[3030],U[3030];
ll ret[3030];
int dp[3030];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	map<ll,vector<int>> ev;
	vector<ll> Ys;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>H[i];
		L[i]=(X[i]-Y[i])-(M-H[i]);
		R[i]=(X[i]-Y[i])+(M-H[i]);
		D[i]=(X[i]+Y[i])-(M-H[i]);
		U[i]=(X[i]+Y[i])+(M-H[i]);
		Ys.push_back(D[i]);
		Ys.push_back(U[i]);
	}
	sort(ALL(Ys));
	Ys.erase(unique(ALL(Ys)),Ys.end());
	FOR(i,N) {
		D[i]=lower_bound(ALL(Ys),D[i])-Ys.begin();
		U[i]=lower_bound(ALL(Ys),U[i])-Ys.begin();
		ev[L[i]].push_back(i);
		ev[R[i]].push_back(i);
	}
	ll pre=0;
	FORR2(x,e,ev) {
		FOR(y,Ys.size()-1) {
			(ret[dp[y]]+=1LL*(Ys[y+1]-Ys[y])%mo*((x-pre)%mo))%=mo;
		}
		FORR(i,e) if(R[i]==x) {
			for(y=D[i];y<U[i];y++) dp[y]--;
		}
		FORR(i,e) if(L[i]==x) {
			for(y=D[i];y<U[i];y++) dp[y]++;
		}
		pre=x;
	}
	for(i=1;i<=N;i++) cout<<ret[i]%mo*(mo+1)/2%mo<<endl;
}

まとめ

演算子を間違えて、方針立った後も意外に時間かかってしまった。