Submission #60066048

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
  const int maxn=1e5+5;
  char str[maxn];
  int sum[2][maxn],vec[maxn];
  inline int main(){
    int n,q;
    cin>>n>>q>>str;
    for(int i=n;i;--i){
      str[i]=str[i-1];
    }
    int tot=0;
    for(int i=1;i<=n;++i){
      sum[0][i]=sum[0][i-1]+(str[i]=='1');
      sum[1][i]=sum[1][i-1]+(str[i]=='2');
      if(str[i]=='/'){
        vec[++tot]=i;
      }
    }
    for(int i=1;i<=q;++i){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
	const int maxn=1e5+5;
	char str[maxn];
	int sum[2][maxn],vec[maxn];
	inline int main(){
		int n,q;
		cin>>n>>q>>str;
		for(int i=n;i;--i){
			str[i]=str[i-1];
		}
		int tot=0;
		for(int i=1;i<=n;++i){
			sum[0][i]=sum[0][i-1]+(str[i]=='1');
			sum[1][i]=sum[1][i-1]+(str[i]=='2');
			if(str[i]=='/'){
				vec[++tot]=i;
			}
		}
		for(int i=1;i<=q;++i){
			int l,r;
			cin>>l>>r;
			int L=lower_bound(vec+1,vec+tot+1,l)-vec;
			int R=upper_bound(vec+1,vec+tot+1,r)-vec-1;
			if(L>R){
				cout<<"0\n";
				continue;
			}
			int u=L,v=R;
			while(L<R){
				int mid=(L+R)>>1;
				if(sum[0][vec[mid]]-sum[0][l-1]>=sum[1][r]-sum[1][vec[mid]]){
					R=mid;
				}
				else{
					L=mid+1;
				}
			}
			int ans=min(sum[0][vec[L]]-sum[0][l-1],sum[1][r]-sum[1][vec[L]]);
			L=u,R=v;
			while(L<R){
				int mid=(L+R+1)>>1;
				if(sum[0][vec[mid]]-sum[0][l-1]<=sum[1][r]-sum[1][vec[mid]]){
					L=mid;
				}
				else{
					R=mid-1;
				}
			}
			ans=max(ans,min(sum[0][vec[L]]-sum[0][l-1],sum[1][r]-sum[1][vec[L]]));
			cout<<(ans<<1)+1<<"\n";
		}
		return 0;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	SOLUTION::main();
	return 0;
}

Submission Info

Judge Result