oj.uz

Submission #556193

# Submission time Handle Problem Language Result Execution time Memory
556193 2022-05-02T15:00:47 Z Alexandruabcde Election (BOI18_election) C++14
0 / 100
 2 ms 468 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -