oj.uz

Submission #707534

# Submission time Handle Problem Language Result Execution time Memory
707534 2023-03-09T07:50:55 Z ToroTN Election (BOI18_election) C++14
100 / 100
 462 ms 27332 KB 
#include<bits/stdc++.h>
using namespace std;
int n,t,x,y;
char s[500005];
struct node
{
    int l,r,sum,ans;
} seg[2000005];
node merge(node lft,node rht)
{
    node res;
    res.sum=lft.sum+rht.sum;
    res.l=max(lft.l,lft.sum+rht.l);
    res.r=max(rht.r,rht.sum+lft.r);
    res.ans=max({lft.l+rht.r,lft.ans+rht.sum,rht.ans+lft.sum});
    return res;
}
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        if(s[st]=='T')
        {
            seg[tree].l=seg[tree].r=seg[tree].sum=seg[tree].ans=1;
        }else
        {
            seg[tree].l=seg[tree].r=seg[tree].ans=0;
            seg[tree].sum=-1;
        }
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=merge(seg[2*tree],seg[2*tree+1]);
}
node query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)
    {
        return {0,0,0,0};
    }
    if(st>=l&&ed<=r)
    {
        return seg[tree];
    }
    return merge(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r));
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> s+1;
    cin >> t;
    build(1,1,n);
    while(t--)
    {
        cin >> x >> y;
        printf("%d\n",query(1,1,n,x,y).ans);
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     cin >> n >> s+1;
      |                 ~^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 46 ms 4688 KB Output is correct
7 Correct 46 ms 4808 KB Output is correct
8 Correct 49 ms 5624 KB Output is correct
9 Correct 44 ms 5680 KB Output is correct
10 Correct 46 ms 5572 KB Output is correct
11 Correct 46 ms 5760 KB Output is correct
12 Correct 46 ms 5720 KB Output is correct
13 Correct 49 ms 5796 KB Output is correct
14 Correct 47 ms 5708 KB Output is correct
15 Correct 47 ms 5680 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 46 ms 4688 KB Output is correct
7 Correct 46 ms 4808 KB Output is correct
8 Correct 49 ms 5624 KB Output is correct
9 Correct 44 ms 5680 KB Output is correct
10 Correct 46 ms 5572 KB Output is correct
11 Correct 46 ms 5760 KB Output is correct
12 Correct 46 ms 5720 KB Output is correct
13 Correct 49 ms 5796 KB Output is correct
14 Correct 47 ms 5708 KB Output is correct
15 Correct 47 ms 5680 KB Output is correct
16 Correct 450 ms 26256 KB Output is correct
17 Correct 402 ms 26372 KB Output is correct
18 Correct 414 ms 26316 KB Output is correct
19 Correct 340 ms 25912 KB Output is correct
20 Correct 440 ms 25408 KB Output is correct
21 Correct 444 ms 27288 KB Output is correct
22 Correct 427 ms 27068 KB Output is correct
23 Correct 445 ms 27332 KB Output is correct
24 Correct 441 ms 26976 KB Output is correct
25 Correct 462 ms 26472 KB Output is correct