oj.uz

Submission #942791

# Submission time Handle Problem Language Result Execution time Memory
942791 2024-03-11T04:44:57 Z 12345678 Election (BOI18_election) C++17
100 / 100
 422 ms 41320 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, vl[nx], q, l, r;
string str;

struct segtree
{
    struct node
    {
        int l, r, sm, ans;
        node(): l(0), r(0), sm(0), ans(-1e9){}
        node(int x): l(max(0, x)), r(max(0, x)), sm(x), ans(max(0, x)){}
        friend node operator+(const node &a, const node &b)
        {
            if (a.ans==-1e9) return b;
            if (b.ans==-1e9) return a;
            node res;
            res.l=max(a.l, a.sm+b.l);
            res.r=max(a.r+b.sm, b.r);
            res.sm=a.sm+b.sm;
            res.ans=max({a.ans+b.sm, a.sm+b.ans, a.l+b.r});
            return res;
        }
    } d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(vl[l]), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
        //cout<<l<<' '<<r<<' '<<d[i].l<<' '<<d[i].r<<' '<<d[i].sm<<' '<<d[i].ans<<'\n';
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>str;
    str=' '+str;
    for (int i=1; i<=n; i++) vl[i]=(str[i]=='T')?1:-1;
    s.build(1, n, 1);
    cin>>q;
    while (q--) cin>>l>>r, cout<<s.query(1, n, 1, l, r).ans<<'\n';
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33392 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33392 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 48 ms 34416 KB Output is correct
7 Correct 49 ms 34464 KB Output is correct
8 Correct 48 ms 34392 KB Output is correct
9 Correct 42 ms 34384 KB Output is correct
10 Correct 49 ms 34460 KB Output is correct
11 Correct 49 ms 34708 KB Output is correct
12 Correct 48 ms 34612 KB Output is correct
13 Correct 48 ms 34636 KB Output is correct
14 Correct 55 ms 34492 KB Output is correct
15 Correct 56 ms 34636 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 8 ms 33392 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 48 ms 34416 KB Output is correct
7 Correct 49 ms 34464 KB Output is correct
8 Correct 48 ms 34392 KB Output is correct
9 Correct 42 ms 34384 KB Output is correct
10 Correct 49 ms 34460 KB Output is correct
11 Correct 49 ms 34708 KB Output is correct
12 Correct 48 ms 34612 KB Output is correct
13 Correct 48 ms 34636 KB Output is correct
14 Correct 55 ms 34492 KB Output is correct
15 Correct 56 ms 34636 KB Output is correct
16 Correct 404 ms 40232 KB Output is correct
17 Correct 359 ms 39968 KB Output is correct
18 Correct 372 ms 40280 KB Output is correct
19 Correct 321 ms 39928 KB Output is correct
20 Correct 413 ms 39416 KB Output is correct
21 Correct 418 ms 41132 KB Output is correct
22 Correct 404 ms 41104 KB Output is correct
23 Correct 400 ms 41320 KB Output is correct
24 Correct 398 ms 40956 KB Output is correct
25 Correct 422 ms 40520 KB Output is correct