oj.uz

Submission #934949

# Submission time Handle Problem Language Result Execution time Memory
934949 2024-02-28T08:58:29 Z MisterReaper Election (BOI18_election) C++17
100 / 100
 403 ms 44956 KB 
#include <bits/stdc++.h>
using i64 = long long;

struct Info {
    int mxpre, mxsuf, sum, ans;
    Info() { *this = Info(0); } 
    Info(int x) {
        ans = mxsuf = mxpre = std::max(0, x);
        sum = x;
    }
};

Info operator+(Info lhs, Info rhs) {
    Info res;
    res.mxpre = std::max(lhs.mxpre, lhs.sum + rhs.mxpre);
    res.mxsuf = std::max(lhs.mxsuf + rhs.sum, rhs.mxsuf);
    res.sum = lhs.sum + rhs.sum;
    res.ans = std::max({lhs.ans + rhs.sum, lhs.sum + rhs.ans, lhs.mxpre + rhs.mxsuf});
    return res;
}

template<typename T>
struct SegTree {
    int n;
    std::vector<T> tree;
    SegTree(int n) : n(n) {
        tree.resize(4 * n);
    }

    void set(int node, int l, int r, int p, T v) {
        if(l == r) {
            tree[node] = v;
            return;
        }

        int mid = (l + r) / 2;
        if(p <= mid) {
            set(node * 2, l, mid, p, v);
        } else {
            set(node * 2 + 1, mid + 1, r, p, v);
        }
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void set(int p, T v) {
        set(1, 0, n - 1, p, v);
    }

    T query(int node, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return tree[node];
        }

        int mid = (l + r) / 2;
        if(qr <= mid) {
            return query(node * 2, l, mid, ql, qr);
        } else if(mid + 1 <= ql) {
            return query(node * 2 + 1, mid + 1, r, ql, qr);
        }
        return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
    }

    T query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    SegTree<Info> st(n);
    std::vector<int> v(n);
    for(int i = 0; i < n; i++) {
        v[i] = (s[i] == 'T' ? 1 : -1);
        st.set(i, Info(v[i]));
    }

    int q;
    std::cin >> q;

    for(int _ = 0; _ < q; _++) {
        int l, r;
        std::cin >> l >> r;
        l--; r--;
        std::cout << st.query(l, r).ans << "\n";
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 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 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 44 ms 6480 KB Output is correct
7 Correct 41 ms 6408 KB Output is correct
8 Correct 43 ms 6236 KB Output is correct
9 Correct 36 ms 6388 KB Output is correct
10 Correct 41 ms 6284 KB Output is correct
11 Correct 42 ms 6484 KB Output is correct
12 Correct 43 ms 6504 KB Output is correct
13 Correct 42 ms 6572 KB Output is correct
14 Correct 46 ms 6496 KB Output is correct
15 Correct 43 ms 6508 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 44 ms 6480 KB Output is correct
7 Correct 41 ms 6408 KB Output is correct
8 Correct 43 ms 6236 KB Output is correct
9 Correct 36 ms 6388 KB Output is correct
10 Correct 41 ms 6284 KB Output is correct
11 Correct 42 ms 6484 KB Output is correct
12 Correct 43 ms 6504 KB Output is correct
13 Correct 42 ms 6572 KB Output is correct
14 Correct 46 ms 6496 KB Output is correct
15 Correct 43 ms 6508 KB Output is correct
16 Correct 400 ms 44168 KB Output is correct
17 Correct 333 ms 43496 KB Output is correct
18 Correct 361 ms 43748 KB Output is correct
19 Correct 303 ms 43240 KB Output is correct
20 Correct 380 ms 42832 KB Output is correct
21 Correct 403 ms 44956 KB Output is correct
22 Correct 369 ms 44696 KB Output is correct
23 Correct 377 ms 44940 KB Output is correct
24 Correct 397 ms 44520 KB Output is correct
25 Correct 369 ms 43904 KB Output is correct