Submission #129990

#	Time	Username	Problem	Language	Result	Execution time	Memory
129990		Vardanyan	Election (BOI18_election)	C++14	0 / 100	29 ms	23932 KiB

election

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

const int N = 500*1000+5;
int pref[N];
int suf[N];
int a[N];
int t[4*N][3];
void update(int ind,int v,int s,int e,int l,int r,int val){
    if(l>r) return;
    if(s == l && e == r){
        t[v][ind] = val;
        return;
    }
    int m = (s+e)/2;
    update(ind,v*2,s,m,l,min(m,r),val);
    update(ind,v*2+1,m+1,e,max(l,m+1),r,val);
    t[v][ind] = min(t[v*2][ind],t[v*2+1][ind]);
}
int get(int ind,int v,int s,int e,int l,int r){
    if(l>r) return 1000*1000*1000+5;
    if(s == l && e == r) return t[v][ind];
    int m = (s+e)/2;
    return min(get(ind,v*2,s,m,l,min(m,r)),
           get(ind,v*2+1,m+1,e,max(l,m+1),r));
}
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    memset(t,63,sizeof(t));
    for(int i = 0;i<s.length();i++){
        if(s[i] == 'C') a[i+1] = 1;
        else a[i+1] = -1;
        pref[i+1] = pref[i]+a[i+1];
        update(0,1,1,n,i+1,i+1,pref[i+1]);
    }
    for(int i = s.length()-1;i>=0;i--){
        if(s[i] == 'C') a[i+1] = 1;
        else a[i+1] = -1;
        suf[i+1] = suf[i+2]+a[i+1];
        update(1,1,1,n,i+1,i+1,suf[i+1]);
    }
  //  cout<<get(0,1,1,n,1,n)<<endl;
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int ans = 0;
        ans = max(ans,-(get(0,1,1,n,l,r)-pref[l-1]));
        ans = max(ans,-(get(1,1,1,n,l,r)-suf[r+1]));
        cout<<ans<<endl;
    }

    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.length();i++){
                   ~^~~~~~~~~~~

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