oj.uz

Submission #960451

# Submission time Handle Problem Language Result Execution time Memory
960451 2024-04-10T13:29:32 Z Beerus13 Election (BOI18_election) C++14
100 / 100
 456 ms 42876 KB 
#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

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.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31576 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 8 ms 31580 KB Output is correct
5 Correct 7 ms 31804 KB Output is correct
6 Correct 50 ms 33048 KB Output is correct
7 Correct 47 ms 33044 KB Output is correct
8 Correct 45 ms 32844 KB Output is correct
9 Correct 43 ms 33076 KB Output is correct
10 Correct 51 ms 33008 KB Output is correct
11 Correct 49 ms 33204 KB Output is correct
12 Correct 50 ms 33176 KB Output is correct
13 Correct 49 ms 33108 KB Output is correct
14 Correct 52 ms 33196 KB Output is correct
15 Correct 51 ms 33100 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31576 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 8 ms 31580 KB Output is correct
5 Correct 7 ms 31804 KB Output is correct
6 Correct 50 ms 33048 KB Output is correct
7 Correct 47 ms 33044 KB Output is correct
8 Correct 45 ms 32844 KB Output is correct
9 Correct 43 ms 33076 KB Output is correct
10 Correct 51 ms 33008 KB Output is correct
11 Correct 49 ms 33204 KB Output is correct
12 Correct 50 ms 33176 KB Output is correct
13 Correct 49 ms 33108 KB Output is correct
14 Correct 52 ms 33196 KB Output is correct
15 Correct 51 ms 33100 KB Output is correct
16 Correct 456 ms 41904 KB Output is correct
17 Correct 351 ms 41604 KB Output is correct
18 Correct 363 ms 41860 KB Output is correct
19 Correct 309 ms 41212 KB Output is correct
20 Correct 393 ms 40968 KB Output is correct
21 Correct 426 ms 42796 KB Output is correct
22 Correct 401 ms 42688 KB Output is correct
23 Correct 413 ms 42876 KB Output is correct
24 Correct 424 ms 42444 KB Output is correct
25 Correct 431 ms 41976 KB Output is correct