oj.uz

Submission #912410

# Submission time Handle Problem Language Result Execution time Memory
912410 2024-01-19T12:16:04 Z Trisanu_Das Election (BOI18_election) C++17
100 / 100
 424 ms 27976 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct A {
    int L,R,sum,ans;
} s[1<<20];
 
int n;
char c[500001];
 
A merge(A a, A b) {
    A res;
    res.L=max(a.L,a.sum+b.L);
    res.R=max(b.R,b.sum+a.R);
    res.sum=a.sum+b.sum;
    res.ans=max({a.L+b.R,a.ans+b.sum,b.ans+a.sum});
    return res;
}
 
void build(int l, int r, int idx) {
    if (l==r) {
        if (c[l]=='T') s[idx]={1,1,1,1};
        else s[idx]={0,0,-1,0};
    } else {
        int mid=(l+r)/2;
        build(l,mid,2*idx);
        build(mid+1,r,2*idx+1);
        s[idx]=merge(s[2*idx],s[2*idx+1]);
    }
}
 
A query(int l, int r, int idx, int x, int y) {
    if (x>r || y<l) return {0,0,0,0};
    if (x<=l && r<=y) return s[idx];
    int mid=(l+r)/2;
    return merge(query(l,mid,2*idx,x,y),query(mid+1,r,2*idx+1,x,y));
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>c[i];
    build(1,n,1);
    int q; cin>>q;
    while (q--) {
        int a,b; cin>>a>>b;
        cout<<query(1,n,1,a,b).ans<<"\n";
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 45 ms 7252 KB Output is correct
7 Correct 38 ms 7760 KB Output is correct
8 Correct 49 ms 8016 KB Output is correct
9 Correct 33 ms 7764 KB Output is correct
10 Correct 39 ms 7760 KB Output is correct
11 Correct 39 ms 7768 KB Output is correct
12 Correct 42 ms 7796 KB Output is correct
13 Correct 39 ms 7972 KB Output is correct
14 Correct 39 ms 7752 KB Output is correct
15 Correct 42 ms 7756 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 45 ms 7252 KB Output is correct
7 Correct 38 ms 7760 KB Output is correct
8 Correct 49 ms 8016 KB Output is correct
9 Correct 33 ms 7764 KB Output is correct
10 Correct 39 ms 7760 KB Output is correct
11 Correct 39 ms 7768 KB Output is correct
12 Correct 42 ms 7796 KB Output is correct
13 Correct 39 ms 7972 KB Output is correct
14 Correct 39 ms 7752 KB Output is correct
15 Correct 42 ms 7756 KB Output is correct
16 Correct 392 ms 26820 KB Output is correct
17 Correct 305 ms 26528 KB Output is correct
18 Correct 368 ms 26868 KB Output is correct
19 Correct 278 ms 26172 KB Output is correct
20 Correct 403 ms 26060 KB Output is correct
21 Correct 364 ms 27664 KB Output is correct
22 Correct 354 ms 27632 KB Output is correct
23 Correct 390 ms 27976 KB Output is correct
24 Correct 424 ms 27496 KB Output is correct
25 Correct 414 ms 27028 KB Output is correct