제출 #1039459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039459		vjudge1	Election (BOI18_election)	C++17	0 / 100	1 ms	600 KiB

election

#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.s, 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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18