Submission #707471

#	Time	Username	Problem	Language	Result	Execution time	Memory
707471		ToroTN	Election (BOI18_election)	C++14	0 / 100	3 ms	340 KiB

election

#include<bits/stdc++.h>
using namespace std;
int n,l[500005],r[500005],t,x,y,seg1[2000005],seg2[2000005];
char s[500005];
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        seg1[tree]=l[st];
        seg2[tree]=r[st];
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg1[tree]=min(seg1[2*tree],seg1[2*tree+1]);
    seg2[tree]=min(seg2[2*tree],seg2[2*tree+1]);
}
int query1(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)return 1e9;
    if(st>=l&&ed<=r)return seg1[tree];
    return min(query1(2*tree,st,md,l,r),query1(2*tree+1,md+1,ed,l,r));
}
int query2(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)return 1e9;
    if(st>=l&&ed<=r)return seg2[tree];
    return min(query2(2*tree,st,md,l,r),query2(2*tree+1,md+1,ed,l,r));
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    cin >> s+1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='C')
        {
            l[i]=l[i-1]+1;
        }else
        {
            l[i]=l[i-1]-1;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='C')
        {
            r[i]=r[i+1]+1;
        }else
        {
            r[i]=r[i+1]-1;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%d %d\n",l[i],r[i]);
    }*/
    build(1,1,n);
    //printf("%d %d\n",seg1[1],seg2[1]);
    cin >> t;
    while(t--)
    {
        cin >> x >> y;
        printf("%d\n",-min(query1(1,1,n,x,y)-l[x-1],query2(1,1,n,x,y)-r[y+1]));
    }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     cin >> s+1;
      |            ~^~

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