Submission #934949

#	Time	Username	Problem	Language	Result	Execution time	Memory
934949		MisterReaper	Election (BOI18_election)	C++17	100 / 100	403 ms	44956 KiB

election

#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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18