Submission #683012

#	Time	Username	Problem	Language	Result	Execution time	Memory
683012		Duy_e	Election (BOI18_election)	C++14	100 / 100	453 ms	29260 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 5e5 + 5;

struct node {
    int l_max, r_max, ans, sum;

    node operator +(node other) {
        node ret;
        ret.l_max = max(l_max, sum + other.l_max);
        ret.r_max = max(other.r_max, other.sum + r_max);
        ret.sum = other.sum + sum;
        ret.ans = max(max(ans + other.sum, sum + other.ans), l_max + other.r_max);
        return ret;
    }
} st[4 * N];

int a[N], n;

void build(int id, int l, int r) {
    if (l == r) {
        ll val = max(0, a[l]);
        st[id] = {val, val, val, a[l]};
        return;
    }

    int mid = l + r >> 1;
    build(id << 1, l , mid); build(id << 1 | 1, mid + 1, r);
    st[id] = st[id << 1] + st [id << 1 | 1];
}

node query(int id, int l, int r, int lef, int rig) {
    if (l > rig || r < lef) return {0, 0, 0, 0};
    if (lef <= l && r <= rig) return st[id];
    int mid = l + r >> 1;
    return query(id << 1, l, mid, lef, rig) + query(id << 1 | 1, mid + 1, r, lef, rig); 
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, 1, n) {
        char ch;
        cin >> ch;
        if (ch == 'T') a[i] = 1; else a[i] = -1;
    }

    build(1, 1, n);

    ll q, l, r;
    cin >> q;
    while (q --) {
        cin >> l >> r;
        cout << query(1, 1, n, l, r).ans << '\n';
    }

    return 0;
}  

Compilation message (stderr)

election.cpp: In function 'void build(int, int, int)':
election.cpp:31:19: warning: narrowing conversion of 'val' from 'long long int' to 'int' [-Wnarrowing]
   31 |         st[id] = {val, val, val, a[l]};
      |                   ^~~
election.cpp:31:24: warning: narrowing conversion of 'val' from 'long long int' to 'int' [-Wnarrowing]
   31 |         st[id] = {val, val, val, a[l]};
      |                        ^~~
election.cpp:31:29: warning: narrowing conversion of 'val' from 'long long int' to 'int' [-Wnarrowing]
   31 |         st[id] = {val, val, val, a[l]};
      |                             ^~~
election.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~
election.cpp: In function 'node query(int, int, int, int, int)':
election.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~

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