Submission #519844

#	Time	Username	Problem	Language	Result	Execution time	Memory
519844		ahmedfouadnew	Election (BOI18_election)	C++17	0 / 100	4 ms	336 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define f first
#define s second
int sum[500005][2],n,q;
int mni[4*500005][2];
string s;
int build(int ni,int ns,int ne,bool d)
{
    if(ns==ne)
    {
        return mni[ni][d]=ns;
    }
    int mid=ns+(ne-ns)/2;
    int x=build(ni*2+1,ns,mid,d);
    int y=build(ni*2+2,mid+1,ne,d);
    if(sum[x][d]>=sum[y][d])
        mni[ni][d]=x;
    else
        mni[ni][d]=y;
    return mni[ni][d];
}
int query(int ni,int ns,int ne,int nl,int nr,bool d)
{
    if(nr<ns||ne<nl)
        return n;
    if(nl<=ns&&ne<=nr)
        return mni[ni][d];
    int mid=ns+(ne-ns)/2;
    int x=query(ni*2+1,ns,mid,nl,nr,d);
    int y=query(ni*2+2,mid+1,ne,nl,nr,d);
    if(sum[x][d]>=sum[y][d])
        return x;
    return y;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(!i)
        {
            sum[i][0]=2*(s[i]=='T')-1;
        }
        else
            sum[i][0]=2*(s[i]=='T')-1+sum[i-1][0];
    }
    for(int i=n-1;i>=0;i--)
    {
        if(i==n-1)
        {
            sum[i][1]=2*(s[i]=='T')-1;
        }
        else
            sum[i][1]=2*(s[i]=='T')-1+sum[i+1][1];
    }
    sum[n][0]=sum[n][1]=-1e9;
    build(0,0,n-1,0);
    build(0,0,n-1,1);
    cin>>q;
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        l--,r--;
        int pr=query(0,0,n-1,l,r,0),sf=query(0,0,n-1,l,r,1);
        int ans=max(sum[pr][0]-(l?0:sum[l-1][0]),sum[sf][1]-(r==n-1?0:sum[r+1][1]));
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:71:44: warning: array subscript -1 is below array bounds of 'long long int [500005][2]' [-Warray-bounds]
   71 |         int ans=max(sum[pr][0]-(l?0:sum[l-1][0]),sum[sf][1]-(r==n-1?0:sum[r+1][1]));
      |                                     ~~~~~~~^
election.cpp:7:5: note: while referencing 'sum'
    7 | int sum[500005][2],n,q;
      |     ^~~

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