Submission #1024524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024524		michified	Election (BOI18_election)	C++17	100 / 100	1094 ms	46740 KiB

election

#include <bits/stdc++.h>
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

struct node_t {
    int mp, ms, tot, ans;
};

string votes;
vector<node_t> st;

void merge(node_t& l, node_t& r, node_t& cur) {
    cur.mp = max(l.mp, r.mp + l.tot);
    cur.ms = max(l.ms + r.tot, r.ms);
    cur.tot = l.tot + r.tot;
    cur.ans = max(max(l.tot + r.ans, l.ans + r.tot), l.mp + r.ms);
}

void build(int id, int l, int r) {
    if (l == r) {
        if (votes[l] == 'T') st[id] = {1, 1, 1, 1};
        else st[id] = {0, 0, -1, 0};
        return;
    }
    int mid = (l + r) / 2;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    merge(st[lid], st[rid], st[id]);
}

node_t quer(int id, int l, int r, int ql, int qr) {
    if (l > qr or r < ql) return {0, 0, 0, 0};
    if (ql <= l and r <= qr) return st[id];
    int mid = (l + r) / 2;
    node_t ret, L = quer(lid, l, mid, ql, qr), R = quer(rid, mid + 1, r, ql, qr);
    merge(L, R, ret);
    return ret;
}

int main() {
    int n, q, i;
    cin >> n >> votes >> q;
    vector<pair<int, int>> ques(q);
    for (i = 0; i < q; i++) cin >> ques[i].first >> ques[i].second;
    st.resize(n * 4);
    build(0, 0, n - 1);
    for (auto& que : ques) {
        que.first--;
        que.second--;
        cout << quer(0, 0, n - 1, que.first, que.second).ans << endl;
    }
    return 0;
}

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