Submission #1118959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118959		Thunnus	Election (BOI18_election)	C++17	100 / 100	702 ms	73572 KiB

election

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using i64 = long long;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct SegTree{
    struct Node{
        int sum, pref, suff, ans;
    };
    vector<Node> st;
    SegTree(int n) : st(4 * n) {}

    inline Node combine(const Node &a, const Node &b){
        Node c;
        c.sum = a.sum + b.sum;
        c.pref = max(a.pref, a.sum + b.pref);
        c.suff = max(b.suff, b.sum + a.suff);
        c.ans = max({a.ans + b.sum, b.ans + a.sum, a.pref + b.suff});
        return c;
    }

    inline void update(int pos, int val, int v, int tl, int tr){
        if(tl == tr){
            if(val == 1) st[v] = {1, 1, 1, 1};
            else st[v] = {-1, 0, 0, 0};
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid){
            update(pos, val, 2 * v, tl, mid);
        }
        else{
            update(pos, val, 2 * v + 1, mid + 1, tr);
        }
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || qr < tl) return {0, 0, 0, 0};
        if(ql <= tl && qr >= tr) return st[v];
        int mid = (tl + tr) / 2;
        return combine(query(ql, qr, 2 * v, tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr));
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, l, r;
    string s;
    cin >> n >> s >> q;
    SegTree st(n);
    for(int i = 0; i < n; i++){
        st.update(i + 1, s[i] == 'T', 1, 1, n);
    }

    while(q--){
        cin >> l >> r;
        cout << st.query(l, r, 1, 1, n).ans << "\n";
    }
    return 0;
}

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