Submission #484518

#	Time	Username	Problem	Language	Result	Execution time	Memory
484518		hoanghq2004	Election (BOI18_election)	C++14	100 / 100	382 ms	28116 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

int n, q;
string s;

struct node {
    int L, R;
    int sum;
    int best;
    node operator + (const node& other) const {
        node ret;
        ret.sum = sum + other.sum;
        ret.L = max(L, sum + other.L);
        ret.R = max(other.R, other.sum + R);
        ret.best = max({L + other.R, best + other.sum, sum + other.best});
        return ret;
    }
} st[2000010];

void build(int id, int L, int R) {
    if (L == R) {
        if (s[L - 1] == 'T') st[id] = {1, 1, 1, 1};
        else st[id] = {0, 0, -1, 0};
        return;
    }
    int mid = L + R >> 1;
    build(id * 2, L, mid);
    build(id * 2 + 1, mid + 1, R);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

node get(int id, int L, int R, int u, int v) {
    if (u <= L && R <= v) return st[id];
    int mid = L + R >> 1;
    if (v <= mid) return get(id * 2, L, mid, u, v);
    if (u > mid) return get(id * 2 + 1, mid + 1, R, u, v);
    return get(id * 2, L, mid, u, v) + get(id * 2 + 1, mid + 1, R, u, v);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    cin >> s;
    build(1, 1, n);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << get(1, 1, n, l, r).best << '\n';
    }
}

Compilation message (stderr)

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

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