oj.uz

Submission #536318

# Submission time Handle Problem Language Result Execution time Memory
536318 2022-03-12T20:41:22 Z Deepesson Election (BOI18_election) C++17
100 / 100
 520 ms 20188 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 66 ms 2996 KB Output is correct
7 Correct 58 ms 3076 KB Output is correct
8 Correct 59 ms 3020 KB Output is correct
9 Correct 54 ms 2908 KB Output is correct
10 Correct 64 ms 2932 KB Output is correct
11 Correct 58 ms 3116 KB Output is correct
12 Correct 59 ms 3136 KB Output is correct
13 Correct 62 ms 3092 KB Output is correct
14 Correct 59 ms 3068 KB Output is correct
15 Correct 59 ms 3020 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 66 ms 2996 KB Output is correct
7 Correct 58 ms 3076 KB Output is correct
8 Correct 59 ms 3020 KB Output is correct
9 Correct 54 ms 2908 KB Output is correct
10 Correct 64 ms 2932 KB Output is correct
11 Correct 58 ms 3116 KB Output is correct
12 Correct 59 ms 3136 KB Output is correct
13 Correct 62 ms 3092 KB Output is correct
14 Correct 59 ms 3068 KB Output is correct
15 Correct 59 ms 3020 KB Output is correct
16 Correct 517 ms 19176 KB Output is correct
17 Correct 452 ms 19248 KB Output is correct
18 Correct 492 ms 19236 KB Output is correct
19 Correct 425 ms 18640 KB Output is correct
20 Correct 520 ms 18472 KB Output is correct
21 Correct 518 ms 20048 KB Output is correct
22 Correct 516 ms 19832 KB Output is correct
23 Correct 519 ms 20188 KB Output is correct
24 Correct 518 ms 19872 KB Output is correct
25 Correct 515 ms 19296 KB Output is correct