Submission #64159

#	Time	Username	Problem	Language	Result	Execution time	Memory
64159		Bodo171	Election (BOI18_election)	C++14	0 / 100	10 ms	376 KiB

election

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=100005;
string str;
int s[nmax];
int n,i,m,st,dr,ans,j,p,take;
int sum(int l,int r)
{
    if(l>r) return 0;
    return s[r]-s[l-1];
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    cin>>str;
    for(i=1;i<=n;i++)
    {
        if(str[i-1]=='C') s[i]=s[i-1]+1;
        else s[i]=s[i-1]-1;
    }
    cin>>m;
    for(int cnt=1;cnt<=m;cnt++)
    {
        cin>>st>>dr;ans=0;
        for(j=st;j<=dr;j++)
           if(str[j-1]=='T')
              {
                  p=j;
                  while(p<=dr&&str[p-1]=='T')
                    p++;
                  p--;
                  take=min(min(sum(st,j-1),sum(p+1,dr)),p-j+1);
                  ans+=(p-j+1-take);
                  j=p;
              }
        cout<<ans<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18