TopCoder SRM 780 : Div1 Medium Prominence

定数倍の差で落ちるの残念。
https://community.topcoder.com/stat?c=problem_statement&pm=16011&rd=17853

問題

左右方向と高さ方向の2軸の地図(左右方向の位置に対する各地点の高さ)が与えられる。
ここで、Prominenceとは、局所的な頂上に対し定義される値で、最寄の自身より高い地点に行くために、一旦下がらなければいけない高度の最小値を示す。
なお、区間内で最高地点の頂点においては、その値は標高そのものとなる。

与えられた地図に対するProminenceの総和を求めよ。

解法

まず、各局所的な頂上に対するProminenceの求め方を考える。
最初に、左右方向の最寄りの自身より標高の高い位置を見つけられたとする。
あとは、それぞれ現在位置とそこの間にある最も標高の低い地点を探すことができれば、左右のうち高い方との差がProminenceになる。

前半パートは、標高の高い順に各地点の処理をしていけば、処理済みの座標をsetに入れておいてlower_boundを取ればよい。
後半はRMQ。
定数倍が割と厳しいので注意。

template<class V,int NV> class RMQ {
private:
	V table[NV+1][1<<NV];
	int LG[1<<NV];
	int NV2;
public:
	static V const def=(1<<30);
	V comp(V l,V r){ return min(l,r);};
	RMQ() {
		int i,x;
		NV2=1<<NV;
		LG[1]=0;
		for(i=2;i<NV2;i++) LG[i]=LG[i/2]+1;
		FOR(i,NV) FOR(x,NV2) table[i][x]=def;
	}
	void set(int x,V v){ table[0][x]=v;}
	void build() {
		int i,j,x,y;
		FOR(i,NV) FOR(x,NV2) table[i+1][x]=comp(table[i][x],(x+(1<<i)<NV2)?table[i][x+(1<<i)]:def);
	}
	V query(int L,int R) { //[L,R),
		L=max(0,L), R=min(R,NV2);
		if(R<=L) return def;
		int WL=LG[R-L];
		return comp(table[WL][L],table[WL][R-(1<<WL)]);
	}
	
};

RMQ<int,20> rmq;

int ng[1010101];
vector<ll> H;
vector<pair<int,int>> V;
set<int> S;
class Prominence {
	public:
	long long sumOfProminences(int N, vector <int> coef, vector <int> idx, vector <int> val) {
		int i;
		FOR(i,1<<20) rmq.set(i,1<<30);
		H.clear();
		V.clear();
		S.clear();
		
		FOR(i,N) {
			int p=i%2;
			ll a=coef[3*p];
			ll b=coef[3*p+1];
			ll c=coef[3*p+2];
			H.push_back(((a*i+b)%1000000007*i+c)%1000000007);
		}
		FOR(i,idx.size()) H[idx[i]]=val[i];
		
		FOR(i,N) {
			ng[i]=0;
			if(i&&H[i-1]>=H[i]) ng[i]=1;
			if(i+1<N&&H[i+1]>=H[i]) ng[i]=1;
			V.push_back({-H[i],i});
			rmq.set(i,H[i]);
		}
		
		rmq.build();
		
		
		S.insert(-1);
		S.insert(N);
		ll ret=0;
		sort(ALL(V));
		FOR(i,V.size()) {
			int j=i;
			while(j<V.size()&&V[j].first==V[i].first) j++;
			for(int x=i;x<j;x++) {
				int a=V[x].second;
				if(ng[a]==0) {
					int ma=0;
					auto it=S.lower_bound(a);
					if(*it!=N) ma=max(ma,rmq.query(a+1,*it));
					it--;
					if(*it!=-1) ma=max(ma,rmq.query(*it+1,a));
					ret+=(-V[i].first)-ma;
				}
			}
			for(int x=i;x<j;x++) {
				int a=V[x].second;
				S.insert(a);
			}
			i=j-1;
		}
		return ret;
		
		
	}
}

まとめ

問題文見たとき、グラディウスIIとか沙羅曼蛇が頭に思い浮かんだおかげで、Prominenceの定義を理解するのに手間取った。