oj.uz

Submission #331760

# Submission time Handle Problem Language Result Execution time Memory
331760 2020-11-30T01:16:41 Z smax Election (BOI18_election) C++17
100 / 100
 564 ms 43416 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

struct Node {
    int pref, suff, sum, ans;

    void leaf(char c) {
        pref = suff = ans = c == 'T';
        sum = c == 'T' ? 1 : -1;
    }

    void pull(Node &a, Node &b) {
        pref = max(a.pref, a.sum + b.pref);
        suff = max(b.suff, b.sum + a.suff);
        sum = a.sum + b.sum;
        ans = max({a.ans + b.sum, b.ans + a.sum, a.pref + b.suff});
    }
};

struct SegmentTree {
    int n;
    string s;
    vector<Node> st;

    SegmentTree(int _n) : n(_n), st(4*n) {
        build(1, 0, n-1);
    }

    SegmentTree(const string &_s) : n(_s.size()), s(_s), st(4*n) {
        build(1, 0, n-1);
    }

    void build(int p, int l, int r) {
        if (l == r) {
            st[p].leaf(s[l]);
            return;
        }

        int m = (l + r) / 2;
        build(2*p, l, m);
        build(2*p+1, m+1, r);
        st[p].pull(st[2*p], st[2*p+1]);
    }

    Node query(int p, int l, int r, int i, int j) {
        if (l == i && r == j)
            return st[p];

        int m = (l + r) / 2;
        if (j <= m)
            return query(2*p, l, m, i, j);
        else if (i > m)
            return query(2*p+1, m+1, r, i, j);
        Node ret, ls = query(2*p, l, m, i, m), rs = query(2*p+1, m+1, r, m+1, j);
        ret.pull(ls, rs);
        return ret;
    }

    int query(int i, int j) {
        return query(1, 0, n-1, i, j).ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    string s;
    cin >> n >> s >> q;
    SegmentTree st(s);
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << st.query(l, r) << "\n";
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 59 ms 6284 KB Output is correct
7 Correct 48 ms 6124 KB Output is correct
8 Correct 53 ms 6124 KB Output is correct
9 Correct 48 ms 6124 KB Output is correct
10 Correct 56 ms 6124 KB Output is correct
11 Correct 54 ms 6252 KB Output is correct
12 Correct 59 ms 6252 KB Output is correct
13 Correct 55 ms 6252 KB Output is correct
14 Correct 57 ms 6272 KB Output is correct
15 Correct 57 ms 6124 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 59 ms 6284 KB Output is correct
7 Correct 48 ms 6124 KB Output is correct
8 Correct 53 ms 6124 KB Output is correct
9 Correct 48 ms 6124 KB Output is correct
10 Correct 56 ms 6124 KB Output is correct
11 Correct 54 ms 6252 KB Output is correct
12 Correct 59 ms 6252 KB Output is correct
13 Correct 55 ms 6252 KB Output is correct
14 Correct 57 ms 6272 KB Output is correct
15 Correct 57 ms 6124 KB Output is correct
16 Correct 545 ms 42400 KB Output is correct
17 Correct 458 ms 42112 KB Output is correct
18 Correct 494 ms 42496 KB Output is correct
19 Correct 401 ms 41960 KB Output is correct
20 Correct 526 ms 41572 KB Output is correct
21 Correct 536 ms 43388 KB Output is correct
22 Correct 543 ms 43264 KB Output is correct
23 Correct 541 ms 43416 KB Output is correct
24 Correct 542 ms 43136 KB Output is correct
25 Correct 564 ms 42624 KB Output is correct