Submission #760458

#	Time	Username	Problem	Language	Result	Execution time	Memory
760458		vjudge1	Election (BOI18_election)	C++17	100 / 100	377 ms	27908 KiB

election

#include <bits/stdc++.h>

            using namespace std;

            int N, Q; string S;
            struct node{
                int sum, pref, suff, res;
            } ST[4 * 500005];

            node merge(node A, 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.res = max({A.pref + B.suff, A.res + B.sum, A.sum + B.res});
                return C;
            }
            void build(int v, int l, int r) {
                if(l == r) {
                    if(S[l] == 'C') ST[v] = {-1, 0, 0, 0};
                    if(S[l] == 'T') ST[v] = {1, 1, 1, 1};
                    return;
                }
                build(v * 2, l, (l + r) / 2);
                build(v * 2 + 1, (l + r) / 2 + 1, r);
                ST[v] = merge(ST[v * 2], ST[v * 2 + 1]);
            }
            node query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return {0, 0, 0, 0};
                if(l >= lo && r <= hi) return ST[v];
                return merge(query(v * 2, l, (l + r) / 2, lo, hi),
                             query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> S >> Q;
                build(1, 0, N - 1);
                while(Q--) {
                    int l, r; cin >> l >> r; l--; r--;
                    cout << query(1, 0, N - 1, l, r).res << "\n";
                }
                return 0;
            }

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