Submission #647100

#	Time	Username	Problem	Language	Result	Execution time	Memory
647100		Alenygam	Election (BOI18_election)	C++14	100 / 100	633 ms	41416 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct Node {
    long long mpf = 0;
    long long msf = 0;
    long long sum = 0;
    long long ans = 0;
};

struct SegTree {
    vector<Node> segTree;
    int realSize;

    SegTree(int N, string &data) {
        realSize = 1<<(int)ceil(log2(N));
        segTree.resize(realSize * 2);

        for (int i = 0; i < N; i++) {
            if (data[i] == 'T') segTree[realSize + i] = {1, 1, 1, 1};
            else segTree[realSize + i] = {0, 0, -1, 0};
        }

        for (int i = realSize - 1; i > 0; i--) {
            segTree[i].mpf = max(segTree[i * 2].mpf, segTree[i * 2].sum + segTree[i * 2 + 1].mpf);
            segTree[i].msf = max(segTree[i * 2 + 1].msf, segTree[i * 2 + 1].sum + segTree[i * 2].msf);
            segTree[i].sum = segTree[i * 2].sum + segTree[i * 2 + 1].sum;
            segTree[i].ans = max({
                segTree[i * 2].sum + segTree[i * 2 + 1].ans,
                segTree[i * 2 + 1].sum + segTree[i * 2].ans,
                segTree[i * 2].mpf + segTree[i * 2 + 1].msf
            });
        }
    }

    Node qry(int u, int left, int right, int l, int r) {
        if (right <= l || left >= r) return Node{0, 0, 0, 0};
        if (left >= l && right <= r) return segTree[u];

        Node lft = qry(u * 2, left, (left + right) / 2, l, r);
        Node rgt = qry(u*2+1, (left + right)/ 2, right, l, r);

        Node ret;
        ret.mpf = max(lft.mpf, lft.sum + rgt.mpf);
        ret.msf = max(rgt.msf, rgt.sum + lft.msf);
        ret.sum = lft.sum + rgt.sum;
        ret.ans = max({
            lft.sum + rgt.ans,
            rgt.sum + lft.ans,
            lft.mpf + rgt.msf
        });
        return ret;
    }
    long long qry(int l, int r) {
        return qry(1, 0, realSize, l, r).ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N; cin >> N;
    string s; cin >> s;
    int Q; cin >> Q;
    SegTree st(N, s);

    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--;

        cout << st.qry(l, r) << '\n';
    }

}

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