Submission #109545

#	Time	Username	Problem	Language	Result	Execution time	Memory
109545		thebes	Election (BOI18_election)	C++14	0 / 100	2 ms	384 KiB

election

#include <bits/stdc++.h>
using namespace std;

const int MN = 5e5+5;
int st[2][3*MN], n, q, i, x, y, arr[MN], brr[MN], ans;
void build(int i,int s,int e){
    if(s!=e){
        build(2*i,s,(s+e)/2);
        build(2*i+1,(s+e)/2+1,e);
        st[0][i]=min(st[0][2*i],st[0][2*i+1]);
        st[1][i]=min(st[1][2*i],st[1][2*i+1]);
    }
    else st[0][i]=arr[s],st[1][i]=brr[s];
}
int qu(int i,int s,int e,int ss,int se,int id){
    if(s>=ss&&e<=se) return st[id][i];
    else if((s+e)/2<ss) return qu(2*i+1,(s+e)/2+1,e,ss,se,id);
    else if((s+e)/2>=se) return qu(2*i,s,(s+e)/2,ss,se,id);
    else return min(qu(2*i,s,(s+e)/2,ss,se,id),qu(2*i+1,(s+e)/2+1,e,ss,se,id));
}
int main(){
    for(scanf("%d",&n),getchar(),i=1;i<=n;i++)
        arr[i]=brr[i]=(getchar()=='C')?1:-1;
    for(i=1;i<=n;i++) arr[i]+=arr[i-1];
    for(i=n;i>=1;i--) brr[i]+=brr[i+1];
    build(1,1,n);
    for(scanf("%d",&q);q;q--){
        scanf("%d%d",&x,&y);
        ans = max(0, -(qu(1,1,n,x,y,0)-arr[x-1]));
        ans = max(ans, max(0, -(qu(1,1,n,x,y,1)-brr[y+1])));
        printf("%d\n",ans);
    }
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:22:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&n),getchar(),i=1;i<=n;i++)
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
election.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&q);q;q--){
         ~~~~~^~~~~~~~~
election.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

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