oj.uz

Submission #683012

# Submission time Handle Problem Language Result Execution time Memory
683012 2023-01-17T14:18:02 Z Duy_e Election (BOI18_election) C++14
100 / 100
 453 ms 29260 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 57 ms 5892 KB Output is correct
7 Correct 42 ms 5836 KB Output is correct
8 Correct 49 ms 5964 KB Output is correct
9 Correct 38 ms 5788 KB Output is correct
10 Correct 44 ms 5712 KB Output is correct
11 Correct 45 ms 5968 KB Output is correct
12 Correct 45 ms 5964 KB Output is correct
13 Correct 45 ms 5972 KB Output is correct
14 Correct 50 ms 5964 KB Output is correct
15 Correct 44 ms 5840 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 57 ms 5892 KB Output is correct
7 Correct 42 ms 5836 KB Output is correct
8 Correct 49 ms 5964 KB Output is correct
9 Correct 38 ms 5788 KB Output is correct
10 Correct 44 ms 5712 KB Output is correct
11 Correct 45 ms 5968 KB Output is correct
12 Correct 45 ms 5964 KB Output is correct
13 Correct 45 ms 5972 KB Output is correct
14 Correct 50 ms 5964 KB Output is correct
15 Correct 44 ms 5840 KB Output is correct
16 Correct 422 ms 28388 KB Output is correct
17 Correct 347 ms 27808 KB Output is correct
18 Correct 393 ms 28252 KB Output is correct
19 Correct 328 ms 27596 KB Output is correct
20 Correct 438 ms 27360 KB Output is correct
21 Correct 428 ms 29240 KB Output is correct
22 Correct 434 ms 29176 KB Output is correct
23 Correct 453 ms 29260 KB Output is correct
24 Correct 438 ms 28904 KB Output is correct
25 Correct 419 ms 28404 KB Output is correct