kmjp's blog

競技プログラミング参加記です

AtCoder ABC #282 (HHKBプログラミングコンテスト2022 Winter) : Ex - Min + Sum

これは似たようなテクを使ったことがあったのでまぁ。
https://atcoder.jp/contests/abc282/tasks/abc282_h

問題

N要素の2つの非負整数列A,Bが与えられる。
1≦L≦R≦Nとなる(L,R)の対のうち、 \displaystyle min(A_L,A_{L+1}, ... , A_R)+sum(B_L,B_{L+1}, ... , B_R) \le Sとなるものは何通りか。

解法

あらかじめBの累積和を取っておく。
A[i]の小さい順に、「区間内の最小値がA[i]となるような区間」に関する数え上げを行う。
今X,YをA[X]≦A[i]となるi未満最大のX、A[Y]<A[i]となるi以上最小のYとする。X<L≦i≦R<YとするL,Rを取れば、minの部分はA[i]に確定する。

R-i<i-Lの場合、Rを総当たりしよう。Rを定めたとき、Bの累積和を二分探索することでLをどこまで小さくできるかを求めることができる。
その場合、それより大きなLでも問題の条件を満たすので、(i-L+1)だけ解に計上する。
i-L≦R-iの場合、反対にLを総当たりすればよい。

int N;
ll S;
ll A[252525],B[252525];
ll BS[252525];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	set<int> did={0,N+1};
	vector<pair<ll,int>> V;
	FOR(i,N) {
		cin>>A[i+1];
		V.push_back({A[i+1],i+1});
	}
	FOR(i,N) {
		cin>>B[i+1];
		BS[i+1]=BS[i]+B[i+1];
	}
	ll ret=0;
	sort(ALL(V));
	FORR2(v,i,V) {
		auto it=did.lower_bound(i);
		int R=*it;
		int L=*--it;
		did.insert(i);
		if(R-i<=i-L) {
			ll a=A[i];
			for(x=i;x<R;x++) {
				a+=B[x];
				if(a>S) break;
				int TL=i;
				for(y=20;y>=0;y--) {
					if(TL-(1<<y)<=L) continue;
					if(BS[x]-BS[TL-(1<<y)-1]+A[i]<=S) TL-=1<<y;
				}
				ret+=i-TL+1;
			}
		}
		else {
			ll a=A[i];
			for(x=i;x>L;x--) {
				a+=B[x];
				if(a>S) break;
				int TR=i;
				for(y=20;y>=0;y--) {
					if(TR+(1<<y)>=R) continue;
					if(a+BS[TR+(1<<y)]-BS[i]<=S) TR+=1<<y;
				}
				ret+=TR-i+1;
			}
		}
		
	}
	cout<<ret<<endl;
}

まとめ

悪くはないんだけど、ちょっと遅かったな…。