Submission #481164

#	Time	Username	Problem	Language	Result	Execution time	Memory
481164		Karabasan	Election (BOI18_election)	C++17	0 / 100	2 ms	344 KiB

election

#include <bits/stdc++.h>

using namespace std;
int n;
string s;
int dizi1[500005];
int dizi2[500005];
int seg1[2000005];
int seg2[2000005];
int segment(int x,int l,int r,int bas,int son)
{
    if(r<bas||l>son)
        return 0;
    if(l>=bas&&r<=son)
        return seg1[x];
    int orta=(l+r)/2;
    return max(segment(x*2,l,orta,bas,son),segment(x*2+1,orta+1,r,bas,son));
}
int segment2(int x,int l,int r,int bas,int son)
{
    if(r<bas||l>son)
        return 0;
    if(l>=bas&&r<=son)
        return seg2[x];
    int orta=(l+r)/2;
    return max(segment2(x*2,l,orta,bas,son),segment2(x*2+1,orta+1,r,bas,son));
}
int build2(int x,int bas,int son)
{
    if(bas==son)
        return seg2[x]=dizi2[bas];
    int orta=(bas+son)/2;
    seg2[2*x]=build2(2*x,bas,orta);
    seg2[2*x+1]=build2(2*x+1,orta+1,son);
        return seg2[x]=max(seg2[2*x],seg2[2*x+1]);

}
int build(int x,int bas,int son)
{
    if(bas==son)
        return seg1[x]=dizi1[bas];
    int orta=(bas+son)/2;
    seg1[2*x]=build(2*x,bas,orta);
    seg1[2*x+1]=build(2*x+1,orta+1,son);
        return seg1[x]=max(seg1[2*x],seg1[2*x+1]);

}
int main()
{
    scanf("%d",&n);
    cin>>s;
    s="U"+s;
    if(s[1]=='C')
        dizi1[1]=-1;
    else dizi1[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]=='C')
            dizi1[i]=dizi1[i-1]-1;
        else dizi1[i]=dizi1[i-1]+1;
    }
    if(s[n]=='C')
        dizi2[n]=-1;
    else dizi2[n]=1;
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='C')
            dizi2[i]=dizi2[i+1]-1;
        else dizi2[i]=dizi2[i+1]+1;
    }
    build(1,1,n);
    build2(1,1,n);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",max(segment(1,1,n,a,b)-dizi1[a-1],segment2(1,1,n,a,b)-dizi2[b+1]));
    }
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
election.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
election.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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