Codeforces Global Round 5 : D. Balanced Playlist

この回5問早解きでえらくレートを稼いでる。
https://codeforces.com/contest/1237/problem/D

問題

N個の曲のリストがある。
それぞれのカッコよさはA[i]とする。
リストの途中から曲を順に再生したとする。再生時リストの末尾に到達した場合、また先頭から再生する。
途中、これまでの再生した曲のカッコよさの最大値の半分以下の曲に遭遇すると、その前に再生を止める。

リストの各位置から再生を始めたとき、何曲再生するかを求めよ。

解法

カッコよさの大きい順に処理する。
今x番から開始するとし、処理済みの、すなわち自身より高いカッコよさの最寄りの曲の位置がy番目とする。
もし、x番からy番の間にカッコよさがA[x]/2未満の曲がある場合、そこで再生が止まる。
その位置はRMQで二分探索すれば求められる。
y番目まで再生がたどり着くことができた場合、そこから先はy番目から始めた場合と同じ曲数が再生できる。

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=(1LL<<40);
	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<ll,18> rmq;

int N;
ll A[201010];
int ret[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ma=0,mi=1LL<<40;
	vector<pair<ll,int>> V;
	FOR(i,N) {
		cin>>A[i];
		A[i]*=2;
		A[i+N]=A[i];
		V.push_back({-A[i],i});
		rmq.set(i,A[i]);
		rmq.set(i+N,A[i]);
	}
	rmq.build();
	
	sort(ALL(V));
	set<int> did;
	FORR(v,V) {
		int cur=v.second;
		int nex=N;
		
		if(did.size()) {
			nex=*did.lower_bound(cur)-cur;
		}
		
		ll val=rmq.query(cur,cur+nex);
		if(val>=A[cur]/2) {
			if(nex==N) ret[cur]=3*N;
			else ret[cur]=ret[cur+nex]+nex;
		}
		else {
			for(i=18;i>=0;i--) if(nex>(1<<i)) {
				ll val=rmq.query(cur,cur+nex-(1<<i));
				if(val<A[cur]/2) nex-=1<<i;
			}
			ret[cur]=nex-1;
		}
		
		ret[cur+N]=ret[cur];
		did.insert(cur);
		did.insert(cur+N);
	}
	
	FOR(i,N) {
		if(ret[i]>=3*N) ret[i]=-1;
		cout<<ret[i]<<" ";
	}
	
}

まとめ

まぁそんな基準で（過去に再生した曲との相対的なカッコよさの割合で）再生を続けるか止めるか選ぶか？という気はするが。