Submission #643286

#	Time	Username	Problem	Language	Result	Execution time	Memory
643286		Kripton	Election (BOI18_election)	C++14	0 / 100	2 ms	596 KiB

election

#include <bits/stdc++.h>
using namespace std;
int rmqst[500001][19],rmqdr[500002][19];
int sumst[500001],sumdr[500002];
char s[500001];
int logue[500001];
int queryst(int a,int b)
{
    int lg=logue[b-a+1];
    return min(sumst[rmqst[b][lg]],sumst[rmqst[a+(1<<lg)-1][lg]]);
}
int querydr(int a,int b)
{
    int lg=logue[b-a+1];
    return min(sumdr[rmqdr[b][lg]],sumdr[rmqdr[a+(1<<lg)-1][lg]]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,j,q,a,b;
    cin>>n>>ws>>(s+1)>>ws;
    for(i=2;i<=n;i++)
        logue[i]=logue[i/2]+1;
    for(i=1;i<=n;i++)
    {
        sumst[i]=sumst[i-1]+(s[i]=='C')-(s[i]=='T');
        rmqst[i][0]=i;
    }
    for(i=n;i>=1;i--)
    {
        sumdr[i]=sumdr[i+1]+(s[i]=='C')-(s[i]=='T');
        rmqdr[i][0]=i;
    }
    for(j=1;j<=logue[n];j++)
        for(i=(1<<j);i<=n;i++)
        {
            if(sumst[rmqst[i][j-1]]<sumst[rmqst[i-(1<<(j-1))][j-1]])
                rmqst[i][j]=rmqst[i][j-1];
            else
                rmqst[i][j]=rmqst[i-(1<<(j-1))][j-1];
            if(sumdr[rmqdr[i][j-1]]<sumdr[rmqdr[i-(1<<(j-1))][j-1]])
                rmqdr[i][j]=rmqdr[i][j-1];
            else
                rmqdr[i][j]=rmqdr[i-(1<<(j-1))][j-1];
        }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>a>>b;
        cout<<max(-(queryst(a,b)-sumst[a-1]),-(querydr(a,b)-sumdr[b+1]))<<'\n';
    }
    return 0;
}

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