Submission #960451

#	Time	Username	Problem	Language	Result	Execution time	Memory
960451		Beerus13	Election (BOI18_election)	C++14	100 / 100	456 ms	42876 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const int inf = 1e9;

struct node {
    int sum, pre, suf, res;
    node() {
        sum = pre = suf = res = 0;
    }
    node(int x) {
        sum = x;
        pre = max(0, x);
        suf = max(0, x);
        res = max(0, x);
    }
};

node operator + (node &a, node &b) {
    node tmp;
    tmp.sum = a.sum + b.sum;
    tmp.pre = max(a.pre, a.sum + b.pre);
    tmp.suf = max(b.suf, a.suf + b.sum);
    tmp.res = max({a.pre + b.suf, a.sum + b.res, a.res + b.sum});
    return tmp;
}

int n, q;
string s;
node st[N << 2];

void build(int id, int l, int r) {
    if(l == r) {
        if(s[l] == 'C') st[id] = node(-1);
        else st[id].sum = st[id].res = st[id].pre = st[id].suf = 1;
        return;
    }
    int m = l + r >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m + 1, r);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

node get(int u, int v, int id = 1, int l = 1, int r = n) {
    if(u > r || v < l) return node();
    if(u <= l && r <= v) return st[id];
    int m = l + r >> 1;
    node L = get(u, v, id << 1, l, m);
    node R = get(u, v, id << 1 | 1, m + 1, r);
    return L + R;
}

void solve() {
    cin >> n >> s >> q;
    s = ' ' + s;
    build(1, 1, n);
    while(q--) {
        int l, r; cin >> l >> r;
        cout << get(l, r).res << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'void build(int, int, int)':
election.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int m = l + r >> 1;
      |             ~~^~~
election.cpp: In function 'node get(int, int, int, int, int)':
election.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int m = l + r >> 1;
      |             ~~^~~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18