Submission #888948

#	Time	Username	Problem	Language	Result	Execution time	Memory
888948		chanhchuong123	Election (BOI18_election)	C++14	100 / 100	337 ms	20216 KiB

election

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#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 (stderr)

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

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