提出 #70488354

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=1e7+5;
string s;
int n;
//store sum, max pf, min pf
typedef array<int,3> arin;
const int ts=1048576;
arin a[ts];
arin zero;
arin merge(arin x,arin y){
	arin z;
	z[0]=x[0]+y[0];
	z[1]=max(x[1],x[0]+y[1]);
	z[2]=min(x[2],x[0]+y[2]);
	return z;;
}
void build(int id,int l,int r){
	if(l==r){
		if(s[l]=='A') a[id]={1,1,0};
		else a[id]={-1,0,-1};
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	a[id]=merge(a[id*2],a[id*2+1]);
}/*
int findl(int id,int l,int r,int ql,int qr,arin z){
	if(l==r){
		return l;
	}
	if(ql<=l)
	int mid=(l+r)/2;
	auto w=merge(z,arin[id*2]);
	if(w[2]<0) return findl(id*2,l,mid,ql,qr,z);
	else 
}*/
arin qry(int id,int l,int r,int ql,int qr){
	
	if(l>qr || r<ql || ql>qr) return zero;
	if(ql<=l && r<=qr) return a[id];
	int mid=(l+r)/2;
	return merge(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> s;n=s.size();s='?'+s;
	build(1,1,n);
	int q;cin >> q;
	for(int i=1; i<=q ;i++){
		int l,r;cin >> l >> r;
		arin frog=qry(1,1,n,l,r);
		int sum=frog[0];
		int cb=-frog[2];
		int ca=sum-frog[2];
		ll ans=1e9;
		for(int seed=0; seed<2 ;seed++){//way 1
			int cur_idb=cb;
			int cur_ida=ca;
			ll cost=ca+cb;
			
			int flag=seed;
			while(cur_idb>0 && cur_ida>0){
				flag^=1;
				if(flag%2==0){
					int bl=l,br=r+1;
					while(bl!=br){
						int mid=(bl+br)/2;
						auto tmp=qry(1,1,n,l,mid);
						if(tmp[1]<cur_ida) bl=mid+1;
						else br=mid;
					}
					if(br==r+1){
						cost=1e9;break;
					}
					auto tmp=qry(1,1,n,l,bl);
					if(-tmp[2]>=cur_idb){
						cost=1e9;break;
					}
					cur_idb=-tmp[2];
					cost+=(cur_ida+cur_idb)*2;
				}
				else{
					int al=l-1,ar=r;
					while(al!=ar){
						int mid=(al+ar+1)/2;
						auto tmp=qry(1,1,n,mid,r);
						if(-(tmp[0]-tmp[1])<cur_idb) al=mid-1;
						else ar=mid;
					}
					if(al==l-1){
						cost=1e9;break;
					}
					auto tmp=qry(1,1,n,ar,r);
					if(tmp[0]-tmp[2]>=cur_ida){
						cost=1e9;break;
					}
					cur_ida=tmp[0]-tmp[2];
					cost+=(cur_ida+cur_idb)*2;
				}
				
			}
			ans=min(ans,cost);
		}
		if(ans==1e9) cout << "-1\n";
		else cout << ans << '\n';
	}
}

提出情報

ジャッジ結果