oj.uz

Submission #1039460

# Submission time Handle Problem Language Result Execution time Memory
1039460 2024-07-30T23:07:34 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 394 ms 74996 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 5e5+7;
struct segment_tree
{
    struct node
    {
        ll l, r, opt, s;
        node() {l = r = s = opt = 0;}
        node(ll x)
        {
            if (x < 0)
            {
                l = r = opt = 0;
                s = x;
            }
            else l = r = opt = s = x;
        }
    };
    node merge(node a, node b)
    {
        node x;
        x.l = max(a.l, b.l+a.s);
        x.r = max(b.r, a.r+b.s);
        x.s = a.s + b.s;
        x.opt = max({a.l+b.r, b.opt+a.s, a.opt+b.s});
        return x;
    }
    vector<node> st;
    string s;
    segment_tree(string ss) {s = ss; st.resize((s.size()+7)<<2);}
    void build(ll id, ll l, ll r)
    {
        if (l == r) {st[id] = node((s[l] == 'C' ? -1 : 1)); return;}
        ll m = (r+l)>>1;
        build(id<<1,l,m); build(id<<1|1,m+1,r);
        st[id] = merge(st[id<<1],st[id<<1|1]);
    }
    node get(ll id, ll l, ll r, ll u, ll v)
    {
        if (r < u || v < l) return node();
        if (u <= l && r <= v) return st[id];
        ll m = (r+l)>>1;
        return merge(get(id<<1,l,m,u,v),get(id<<1|1,m+1,r,u,v));
    }
};
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    ll n; cin >> n;
    string s; cin >> s; s = '$' + s;
    segment_tree st(s);
    st.build(1,1,n);
    ll q; cin >> q;
    while (q--)
    {
        ll l, r; cin >> l >> r;
        cout << st.get(1,1,n,l,r).opt << '\n';
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 35 ms 10576 KB Output is correct
7 Correct 33 ms 10572 KB Output is correct
8 Correct 33 ms 10484 KB Output is correct
9 Correct 30 ms 10324 KB Output is correct
10 Correct 43 ms 10320 KB Output is correct
11 Correct 35 ms 10584 KB Output is correct
12 Correct 35 ms 10632 KB Output is correct
13 Correct 36 ms 10576 KB Output is correct
14 Correct 37 ms 10568 KB Output is correct
15 Correct 35 ms 10572 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 35 ms 10576 KB Output is correct
7 Correct 33 ms 10572 KB Output is correct
8 Correct 33 ms 10484 KB Output is correct
9 Correct 30 ms 10324 KB Output is correct
10 Correct 43 ms 10320 KB Output is correct
11 Correct 35 ms 10584 KB Output is correct
12 Correct 35 ms 10632 KB Output is correct
13 Correct 36 ms 10576 KB Output is correct
14 Correct 37 ms 10568 KB Output is correct
15 Correct 35 ms 10572 KB Output is correct
16 Correct 348 ms 73972 KB Output is correct
17 Correct 316 ms 73588 KB Output is correct
18 Correct 302 ms 73980 KB Output is correct
19 Correct 269 ms 73464 KB Output is correct
20 Correct 370 ms 73208 KB Output is correct
21 Correct 394 ms 74996 KB Output is correct
22 Correct 334 ms 74744 KB Output is correct
23 Correct 358 ms 74992 KB Output is correct
24 Correct 380 ms 74612 KB Output is correct
25 Correct 358 ms 74136 KB Output is correct