Submission #536318

#	Time	Username	Problem	Language	Result	Execution time	Memory
536318		Deepesson	Election (BOI18_election)	C++17	100 / 100	520 ms	20188 KiB

election

#include <bits/stdc++.h>
#define MAX 505000
struct node {
    int prefl,prefr;
    int tot,ans;
};
node tab[MAX*4];
node neutro;
node merge(node a,node b){
    if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
    node c;
    c.tot=a.tot+b.tot;
    c.prefl=std::max(a.tot+b.prefl,a.prefl);
    c.prefr=std::max(b.tot+a.prefr,b.prefr);
    c.ans=std::max(std::max(a.ans+b.tot,a.tot+b.ans),a.prefl+b.prefr);
    return c;
}
void update(int t,node k,int la=0,int ra=MAX-1,int pos=1){
    if(ra<t||la>t)return;
    if(la==ra){
        tab[pos]=k;
        return;
    }
    int m = (la+ra)/2;
    update(t,k,la,m,pos*2);
    update(t,k,m+1,ra,(pos*2)+1);
    tab[pos]=merge(tab[pos*2],tab[(pos*2)+1]);
}
node query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(ra<l||la>r)return neutro;
    if(la>=l&&ra<=r){
        return tab[pos];
    }
    int m = (la+ra)/2;
    return merge(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}
node neg,pos;
int main()
{
    neg.ans=1;
    neg.prefl=neg.prefr=1;
    neg.tot=1;
    pos.ans=0;
    pos.prefl=pos.prefr=0;
    pos.tot=-1;
    neutro.tot=-(1e9);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N;
    std::cin>>N;
    std::string s;
    std::cin >> s;
    for(int i=0;i!=N;++i){
        if(s[i]=='C')update(i,pos);else update(i,neg);
    }
    int Q;
    std::cin>>Q;
    for(int i=0;i!=Q;++i){
        int l,r;
        std::cin>>l>>r;--l;--r;
        node ans = query(l,r);
        std::cout<<ans.ans<<"\n";
    }
}

Compilation message (stderr)

election.cpp: In function 'node merge(node, node)':
election.cpp:10:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   10 |     if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
      |     ^~
election.cpp:10:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   10 |     if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
      |                               ^~

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