Submission #855016

#	Time	Username	Problem	Language	Result	Execution time	Memory
855016		ivaziva	Election (BOI18_election)	C++17	0 / 100	5 ms	10588 KiB

election

#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
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18