oj.uz

Submission #855016

# Submission time Handle Problem Language Result Execution time Memory
855016 2023-09-29T20:28:35 Z ivaziva Election (BOI18_election) C++17
0 / 100
 5 ms 10588 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long n;
long long q;
string s;
long long pref1c[MAXN];
long long pref2c[MAXN];
long long pref1t[MAXN];
long long pref2t[MAXN];
long long seg1[MAXN*4];
long long seg2[MAXN*4];

void build1(long long node,long long l,long long r)
{
    if (l==r) seg1[node]=pref1c[l]-pref1t[l];
    else
    {
        long long mid=(l+r)/2;
        build1(2*node,l,mid);
        build1(2*node+1,mid+1,r);
        seg1[node]=min(seg1[2*node],seg1[2*node+1]);
    }
}

void build2(long long node,long long l,long long r)
{
    if (l==r) seg2[node]=pref2c[l]-pref2t[l];
    else
    {
        long long mid=(l+r)/2;
        build2(2*node,l,mid);
        build2(2*node+1,mid+1,r);
        seg2[node]=min(seg2[2*node],seg2[2*node+1]);
    }
}

long long get1(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return LLONG_MAX;
    else if (l==a and r==b) return seg1[node];
    long long mid=(l+r)/2;
    return (min(get1(2*node,l,mid,a,min(b,mid)),get1(2*node+1,mid+1,r,max(a,mid+1),b)));
}

long long get2(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return LLONG_MAX;
    else if (l==a and r==b) return seg2[node];
    long long mid=(l+r)/2;
    return (min(get2(2*node,l,mid,a,min(b,mid)),get2(2*node+1,mid+1,r,max(a,mid+1),b)));
}

int main()
{
    cin>>n>>s;
    pref1c[0]=0,pref1t[0]=0;
    for (long long i=1;i<=n;i++)
    {
        pref1c[i]=pref1c[i-1];
        if (s[i-1]=='C') pref1c[i]++;
        pref1t[i]=pref1t[i-1];
        if (s[i-1]=='T') pref1t[i]++;
    }
    pref2c[n+1]=0,pref2t[n+1]=0;
    for (long long i=n;i>=1;i--)
    {
        pref2c[i]=pref2c[i+1];
        if (s[i-1]=='C') pref2c[i]++;
        pref2t[i]=pref2t[i+1];
        if (s[i-1]=='T') pref2t[i]++;
    }
    build1(1,1,n);
    build2(1,1,n);
    cin>>q;
    for (long long i=1;i<=q;i++)
    {
        long long l,r;
        cin>>l>>r;
        long long val1=get1(1,1,n,l,r);
        long long val2=get2(1,1,n,l,r);
        long long raz1=val1-(pref1c[l-1]-pref1t[l-1]);
        long long raz2=val2-(pref2c[r+1]-pref2t[r+1]);
        if (raz1>=0 and raz2>=0) cout<<0<<endl;
        else if (raz1>=0 and raz2<0) cout<<abs(raz2)<<endl;
        else if (raz1<0 and raz2>=0) cout<<abs(raz1)<<endl;
        else cout<<max(abs(raz1),abs(raz2))<<endl;
    }
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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