oj.uz

Submission #643286

# Submission time Handle Problem Language Result Execution time Memory
643286 2022-09-21T16:50:59 Z Kripton Election (BOI18_election) C++14
0 / 100
 2 ms 596 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -