TopCoder SRM 721 Div1 Easy RememberWords、Div2 Medium RememberWordsEasy

初Hard AC、1桁順位、Highest更新、といいことづくめなのだが、問題が問題だけにいまいち喜べない。
https://community.topcoder.com/stat?c=problem_statement&pm=14707
https://community.topcoder.com/stat?c=problem_statement&pm=14708

問題

d1+d2要素の非負整数列Xのうち、隣接要素の差の絶対値が1以下で、先頭d1要素の和がw1、後半d2要素の和がw2となるようなものがあるか。

解法

D要素で和がWとなるような数列のうち、端に来る可能性があるものを求めよう。
端の要素をvとすると、この数列の上限は(v+(v+D-1))*D/2、下限は(v+(v-(D-1))*D/2 (vがD未満の時はv*(v+1)/2)となるので、Wがその範囲に来るようなvの上限下限を二分探索で求めることができる。

そうするとX[d1-1]とX[d1]に配置可能な値の範囲が求まるので、差が1以下になるような２値を取れるか判定すればよい。

string Y="Possible";
string N="Impossible";

class RememberWords {
	public:
	
	ll LV(ll S,ll D) {
		ll L=max(S-(D-1),0LL);
		return (S+L)*(S-L+1)/2;
	}
	ll RV(ll S,ll D) {
		ll R=S+(D-1);
		return (S+R)*(D)/2;
	}
	
	ll lowest(int D,int W) {
		ll v=(1LL<<30)-1;
		for(int i=29;i>=0;i--) if(RV(v-(1LL<<i),D)>=W) v-=1LL<<i;
		return v;
	}
	ll highest(int D,int W) {
		ll v=0;
		if(W==0) return 0;
		for(int i=29;i>=0;i--) if(LV(v+(1LL<<i),D)<=W) v+=1LL<<i;
		return v;
	}
	
	string isPossible(int d1, int d2, int w1, int w2) {
		ll L1=lowest(d1,w1);
		ll R1=highest(d1,w1);
		ll L2=lowest(d2,w2);
		ll R2=highest(d2,w2);
		cout<<L1<<" "<<R1<<endl;
		cout<<L2<<" "<<R2<<endl;
		
		if(L1>R1 || L2>R2) return N;
		if(R1+1==L2) return Y;
		if(R2+1==L1) return Y;
		if(max(L1,L2)<=min(R1,R2)) return Y;
		return N;
		
	}
}

まとめ

なぜこれ落とした…。