Codeforces #574 Div2 E. OpenStreetMap

簡単目な回だった様子。自分は途中抜けてたこともあり完答間に合わず。
https://codeforces.com/contest/1195/problem/E

問題

N*Mのグリッドが与えられる。
各セルには整数が書かれている。

このうち、A*Bの矩形部分における最小値を取るとき、その総和を求めよ。

解法

縦方向と横方向にそれぞれスライド最小値を使い、各セルから下Aマス、右Bマス以内の最小値を求めれば、あとはそれを足すだけ。
N,Mがそこそこ大きいので、multisetなどでlogを乗せると間に合わない。

int H,W,A,B;
int S[3030][3030];
int T[3030][3030];
int G,X,Y,Z;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	cin>>G>>X>>Y>>Z;
	FOR(y,H) {
		FOR(x,W) {
			S[y][x]=G;
			G=(1LL*G*X+Y)%Z;
		}
	}
	
	FOR(y,H) {
		deque<pair<int,int>> D;
		FOR(x,B) {
			while(D.size() && D.back().first>=S[y][x]) D.pop_back();
			D.push_back({S[y][x],x});
		}
		for(x=0;x+B<=W;x++) {
			while(D.size() && D.front().second<x) D.pop_front();
			T[y][x]=D.front().first;
			while(D.size() && D.back().first>=S[y][x+B]) D.pop_back();
			D.push_back({S[y][x+B],x+B});
		}
	}
	ll ret=0;
	for(x=0;x+B<=W;x++) {
		deque<pair<int,int>> D;
		FOR(y,A) {
			while(D.size() && D.back().first>=T[y][x]) D.pop_back();
			D.push_back({T[y][x],y});
		}
		for(y=0;y+A<=H;y++) {
			while(D.size() && D.front().second<y) D.pop_front();
			ret+=D.front().first;
			while(D.size() && D.back().first>=T[y+A][x]) D.pop_back();
			D.push_back({T[y+A][x],y+A});
		}
	}
	cout<<ret<<endl;
	
}

まとめ

Div2 Eの割に簡単。