oj.uz

Submission #556196

# Submission time Handle Problem Language Result Execution time Memory
556196 2022-05-02T15:02:00 Z Alexandruabcde Election (BOI18_election) C++14
100 / 100
 575 ms 42288 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_pref);

    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
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 56 ms 5848 KB Output is correct
7 Correct 52 ms 5788 KB Output is correct
8 Correct 57 ms 5716 KB Output is correct
9 Correct 65 ms 5828 KB Output is correct
10 Correct 51 ms 5788 KB Output is correct
11 Correct 53 ms 5956 KB Output is correct
12 Correct 58 ms 5904 KB Output is correct
13 Correct 50 ms 5972 KB Output is correct
14 Correct 55 ms 5928 KB Output is correct
15 Correct 52 ms 5872 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 56 ms 5848 KB Output is correct
7 Correct 52 ms 5788 KB Output is correct
8 Correct 57 ms 5716 KB Output is correct
9 Correct 65 ms 5828 KB Output is correct
10 Correct 51 ms 5788 KB Output is correct
11 Correct 53 ms 5956 KB Output is correct
12 Correct 58 ms 5904 KB Output is correct
13 Correct 50 ms 5972 KB Output is correct
14 Correct 55 ms 5928 KB Output is correct
15 Correct 52 ms 5872 KB Output is correct
16 Correct 524 ms 41344 KB Output is correct
17 Correct 458 ms 40852 KB Output is correct
18 Correct 456 ms 41080 KB Output is correct
19 Correct 465 ms 40588 KB Output is correct
20 Correct 491 ms 40452 KB Output is correct
21 Correct 566 ms 42272 KB Output is correct
22 Correct 554 ms 41984 KB Output is correct
23 Correct 492 ms 42288 KB Output is correct
24 Correct 521 ms 41992 KB Output is correct
25 Correct 575 ms 41468 KB Output is correct