Submission #556193

#	Time	Username	Problem	Language	Result	Execution time	Memory
556193		Alexandruabcde	Election (BOI18_election)	C++14	0 / 100	2 ms	468 KiB

election

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 5e5 + 5;

struct Node {
    int sum;
    int Max_pref, Max_suff;
    int ans;
};

Node Comb (Node st, Node dr) {
    Node val;

    val.sum = st.sum + dr.sum;
    val.Max_pref = max(st.Max_pref, st.sum + dr.Max_pref);
    val.Max_suff = max(st.Max_suff + dr.sum, dr.Max_suff);
    val.ans = max(max(st.ans + dr.sum, dr.ans + st.sum), dr.Max_suff + st.Max_suff);

    return val;
}

class SegmentTree {
private:
    vector <Node> arb;
    int sz;

    void Update (int nod, int a, int b, int pos, int value) {
        if (a == b) {
            arb[nod].sum = value;
            arb[nod].Max_pref = max(0, value);
            arb[nod].Max_suff = max(0, value);
            arb[nod].ans = max(0, value);
            return;
        }

        int mij = (a + b) / 2;

        if (pos <= mij) Update(2*nod, a, mij, pos, value);
        else Update(2*nod+1, mij+1, b, pos, value);

        arb[nod] = Comb(arb[2*nod], arb[2*nod+1]);
    }

    Node Query (int nod, int a, int b, int qa, int qb) {
        if (qa <= a && b <= qb) return arb[nod];

        int mij = (a + b) / 2;

        if (qa <= mij && mij < qb) return Comb(Query(2*nod, a, mij, qa, qb),
                                               Query(2*nod+1, mij+1, b, qa, qb));
        else if (qa <= mij) return Query(2*nod, a, mij, qa, qb);
        else return Query(2*nod+1, mij+1, b, qa, qb);
    }

public:
    void Init (int Size) {
        sz = Size;
        arb.resize(4 * sz + 4);
    }

    void Update (int pos, int value) {
        Update(1, 1, sz, pos, value);
    }

    int Answer (int st, int dr) {
        Node aux = Query(1, 1, sz, st, dr);

        return aux.ans;
    }
};

SegmentTree SGT;
int N;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    SGT.Init(N);
    for (int i = 1; i <= N; ++ i ) {
        char ch;
        cin >> ch;

        if (ch == 'C') SGT.Update(i, -1);
        else SGT.Update(i, 1);
    }
}

void Solve () {
    int Q;
    cin >> Q;

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

        cout << SGT.Answer(l, r) << '\n';
    }
}

int main () {
    Read();
    Solve();

    return 0;
}

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