Submission #60088312

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q;
string s;
int a[N],b[N],c[N];
int p[N],tot;
void solve()
{
    cin>>n>>q;
    cin>>s;
    s="0"+s;
    for(int i=1;i<=n;i++) 
    {
        if(s[i]=='1') a[i]=1;
        else if(s[i]=='2') b[i]=1;
        else 
        {
            c[i]=1;
            p[++tot]=i;
        }
        a[i]+=a[i-1];
        b[i]+=b[i-1];
        c[i]+=c[i-1];
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        int ll=lower_bound(p+1,p+tot+1,l)-p;
        int rr=upper_bound(p+1,p+tot+1,r)-p-1;
        int ans=0;
        for(int i=ll;i<=rr;i++)
        {
            int id=p[i];
            int c1=a[id-1]-a[l-1];
            int c2=b[r]-b[id];
            ans=max(ans,2*min(c1,c2)+1);
        }
        cout<<ans<<'\n';
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

Submission Info

Judge Result