oj.uz

Submission #888947

# Submission time Handle Problem Language Result Execution time Memory
888947 2023-12-18T12:55:12 Z chanhchuong123 Election (BOI18_election) C++14
100 / 100
 360 ms 26612 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

const int MAX = 500050;
int nPer;
int nQue;
string S;

struct node {
    int ans, sum, pre, suf;

    node(int value = 0) {
        sum = value;
        ans = max(0, value);
        pre = max(0, value);
        suf = max(0, value);
    }
} st[(1 << 20) + 5];

node combine(const node &lf, const node &rg) {
    node res;

    res.sum = lf.sum + rg.sum;
    res.pre = max(lf.pre, lf.sum + rg.pre);
    res.suf = max(rg.suf, lf.suf + rg.sum);
    res.ans = max({lf.ans + rg.sum, lf.sum + rg.ans, lf.pre + rg.suf});

    return res;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id] = node(S[l] == 'C' ? -1 : +1);
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = combine(st[id << 1], st[id << 1 | 1]);
}

node get(int id, int l, int r, int u, int v) {
    if (l >= u && r <= v) return st[id];

    int mid = l + r >> 1;
    if (u <= mid && mid + 1 <= v)
        return combine(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));

    if (u <= mid)
        return get(id << 1, l, mid, u, v);

    return get(id << 1 | 1, mid + 1, r, u, v);
}

void process(void) {
    cin >> nPer >> S >> nQue; S = ' ' + S;
    build(1, 1, nPer);
    while (nQue--) {
        int l, r; cin >> l >> r;
        cout << get(1, 1, nPer, l, r).ans << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//	freopen(".INP", "r",  stdin);
//	freopen(".OUT", "w", stdout);

    process();

	return 0;
}

Compilation message

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 4 ms 16908 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 5 ms 16884 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 4 ms 16908 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 5 ms 16884 KB Output is correct
6 Correct 37 ms 17996 KB Output is correct
7 Correct 36 ms 18000 KB Output is correct
8 Correct 36 ms 18260 KB Output is correct
9 Correct 29 ms 18008 KB Output is correct
10 Correct 36 ms 18004 KB Output is correct
11 Correct 36 ms 18260 KB Output is correct
12 Correct 36 ms 18252 KB Output is correct
13 Correct 36 ms 18256 KB Output is correct
14 Correct 36 ms 18256 KB Output is correct
15 Correct 36 ms 18192 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 4 ms 16908 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 5 ms 16884 KB Output is correct
6 Correct 37 ms 17996 KB Output is correct
7 Correct 36 ms 18000 KB Output is correct
8 Correct 36 ms 18260 KB Output is correct
9 Correct 29 ms 18008 KB Output is correct
10 Correct 36 ms 18004 KB Output is correct
11 Correct 36 ms 18260 KB Output is correct
12 Correct 36 ms 18252 KB Output is correct
13 Correct 36 ms 18256 KB Output is correct
14 Correct 36 ms 18256 KB Output is correct
15 Correct 36 ms 18192 KB Output is correct
16 Correct 300 ms 25468 KB Output is correct
17 Correct 269 ms 25320 KB Output is correct
18 Correct 309 ms 25532 KB Output is correct
19 Correct 235 ms 25084 KB Output is correct
20 Correct 320 ms 24456 KB Output is correct
21 Correct 343 ms 26364 KB Output is correct
22 Correct 335 ms 26540 KB Output is correct
23 Correct 360 ms 26612 KB Output is correct
24 Correct 314 ms 26104 KB Output is correct
25 Correct 341 ms 25924 KB Output is correct