Submission #571488

#	Time	Username	Problem	Language	Result	Execution time	Memory
571488		choigameautohackrb	Election (BOI18_election)	C++17	28 / 100	3044 ms	2216 KiB

election

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+7;
ll n, Q, a[N], b[N], l, r;
char s;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        a[i]=(s=='C')?1:-1;
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>l>>r;
        ll sum=0,countb=0;
        for(int pos=l;pos<=r;pos++){
            b[pos]=0;
            sum+=a[pos];
            if(sum<0){
                b[pos]--;
                sum=0;
                countb++;
            }
        }
        sum=0;
        for(int pos=r;pos>=l;pos--){
            sum+=a[pos];
            if(sum<0){
                b[pos]++;
                sum=0;
            }
        }
        sum=0;
        for(int pos=l;pos<=r;pos++){
            sum+=b[pos];
            if(sum<0) sum=0;
        }
        cout<<countb+sum<<'\n';
    }
    return 0;
}

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