oj.uz

Submission #902462

# Submission time Handle Problem Language Result Execution time Memory
902462 2024-01-10T12:51:48 Z VMaksimoski008 Election (BOI18_election) C++17
100 / 100
 607 ms 77768 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

struct Node {
    ll sum, ans, pref, suf;
};

struct SegTree {
    int n;
    vector<Node> tree;
    vector<int> v;

    SegTree(vector<int> _v) {
        v = _v;
        n = sz(v);
        tree.resize(4*n+5);
        build(1, 0, n-1);
    }

    Node merge(Node a, Node b) {
        Node res;

        res.sum = a.sum + b.sum;
        res.pref = max({ 0ll, a.pref, a.sum + b.pref });
        res.suf = max({ 0ll, b.suf, b.sum + a.suf });
        res.ans = max({ a.pref + b.suf, a.ans + b.sum, a.sum + b.ans });

        return res;
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u].ans = max(v[tl], 0);
            tree[u].sum = v[tl];
            tree[u].pref = tree[u].suf = max(v[tl], 0);
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    Node query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || tl > r || l > tr) return Node{0, 0, 0, 0};
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(
            query(2*u, tl, tm, l, r),
            query(2*u+1, tm+1, tr, l, r)
        );
    }

    ll query(int l, int r) {
        return query(1, 0, n-1, l, r).ans;
    }
};

int32_t main() {
    setIO();

    int n;
    cin >> n;

    vector<int> v(n);
    for(int i=0; i<n; i++) {
        char ch;
        cin >> ch;
        v[i] = (ch == 'T' ? 1 : -1);
    }

    SegTree tree(v);
    
    int q;
    cin >> q;

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

    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 51 ms 10816 KB Output is correct
7 Correct 57 ms 10888 KB Output is correct
8 Correct 48 ms 10688 KB Output is correct
9 Correct 42 ms 10764 KB Output is correct
10 Correct 55 ms 10720 KB Output is correct
11 Correct 61 ms 11060 KB Output is correct
12 Correct 53 ms 10800 KB Output is correct
13 Correct 51 ms 10836 KB Output is correct
14 Correct 82 ms 11024 KB Output is correct
15 Correct 51 ms 10812 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 51 ms 10816 KB Output is correct
7 Correct 57 ms 10888 KB Output is correct
8 Correct 48 ms 10688 KB Output is correct
9 Correct 42 ms 10764 KB Output is correct
10 Correct 55 ms 10720 KB Output is correct
11 Correct 61 ms 11060 KB Output is correct
12 Correct 53 ms 10800 KB Output is correct
13 Correct 51 ms 10836 KB Output is correct
14 Correct 82 ms 11024 KB Output is correct
15 Correct 51 ms 10812 KB Output is correct
16 Correct 545 ms 76460 KB Output is correct
17 Correct 455 ms 76112 KB Output is correct
18 Correct 454 ms 76404 KB Output is correct
19 Correct 454 ms 75984 KB Output is correct
20 Correct 574 ms 75588 KB Output is correct
21 Correct 517 ms 77572 KB Output is correct
22 Correct 513 ms 77480 KB Output is correct
23 Correct 607 ms 77768 KB Output is correct
24 Correct 572 ms 77260 KB Output is correct
25 Correct 585 ms 76932 KB Output is correct