oj.uz

Submission #831052

# Submission time Handle Problem Language Result Execution time Memory
831052 2023-08-19T16:09:36 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 857 ms 69076 KB 
#include <bits/stdc++.h>
using namespace std;

/// 123

class segtree_t {
       public:
        segtree_t *left, *right;
        int l, r, m, val, lazy;

        segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy(0) {
                if (l == r) return;
                left = new segtree_t(l, m);
                right = new segtree_t(m + 1, r);
        }

        void Update(int s, int t, int x) {
                if (r < s or l > t) return;
                if (s <= l && r <= t) {
                        val += x;
                        lazy += x;
                        return;
                }
                Down();
                left->Update(s, t, x);
                right->Update(s, t, x);
                Up();
        }

        int Get(int s, int t) {
                if (r < s or l > t) return -1e9;
                if (s <= l && r <= t) return val;
                Down();
                return max(left->Get(s, t), right->Get(s, t));
        }

        void Up() {
                val = max(left->val, right->val);
        }

        void Down() {
                left->lazy += lazy;
                right->lazy += lazy;
                right->val += lazy;
                left->val += lazy;
                lazy = 0;
        }
};

template <class T>
class fenwick_t {
       public:
        vector<T> bit;
        int n;

        fenwick_t(int n = 0) : n(n) {
                bit.resize(n + 1, 0);
        }

        void Update(int pos, T val) {
                for (; pos <= n; pos += pos & -pos) {
                        bit[pos] += val;
                }
        }

        T Get(int pos) {
                T res = T(0);
                for (; pos > 0; pos -= pos & -pos) {
                        res += bit[pos];
                }
                return res;
        }

        T Get(int l, int r) {
                return Get(r) - (l ? Get(l - 1) : T(0));
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, q;
        string s;
        cin >> n >> s >> q;
        vector<int> l(q), r(q);
        for (int i = 0; i < q; i++) {
                cin >> l[i] >> r[i];
                l[i]--, r[i]--;
        }
        vector<int> ord(q);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return r[i] < r[j];
        });
        priority_queue<int> pq;
        map<char, int> c;
        c['C'] = -1;
        c['T'] = +1;
        segtree_t *tree = new segtree_t(0, n);
        fenwick_t<int> cnt(n);
        for (int i = 0; i < n; i++) tree->Update(i + 1, n, c[s[i]]);
        vector<int> ans(q, -1);
        for (int i = 0, j = 0; i < n; i++) {
                if (s[i] == 'T') {
                        tree->Update(i + 1, n, -c[s[i]]);
                        pq.emplace(i);
                        cnt.Update(i + 1, +1);
                } else {
                        if (pq.size()) {
                                tree->Update(pq.top() + 1, n, c[s[pq.top()]]);
                                cnt.Update(pq.top() + 1, -1);
                                pq.pop();
                        }
                }
                while (j < q && r[ord[j]] == i) {
                        ans[ord[j]] = cnt.Get(l[ord[j]] + 1, r[ord[j]] + 1) + tree->Get(l[ord[j]], r[ord[j]] + 1) - tree->Get(l[ord[j]], l[ord[j]]);
                        j++;
                }
        }
        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Compilation message

election.cpp: In constructor 'segtree_t::segtree_t(int, int)':
election.cpp:11:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy(0) {
      |                                                 ~~^~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 91 ms 9560 KB Output is correct
7 Correct 73 ms 9496 KB Output is correct
8 Correct 68 ms 9412 KB Output is correct
9 Correct 117 ms 9396 KB Output is correct
10 Correct 69 ms 9420 KB Output is correct
11 Correct 75 ms 9664 KB Output is correct
12 Correct 81 ms 9620 KB Output is correct
13 Correct 74 ms 9784 KB Output is correct
14 Correct 70 ms 9604 KB Output is correct
15 Correct 71 ms 9540 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 91 ms 9560 KB Output is correct
7 Correct 73 ms 9496 KB Output is correct
8 Correct 68 ms 9412 KB Output is correct
9 Correct 117 ms 9396 KB Output is correct
10 Correct 69 ms 9420 KB Output is correct
11 Correct 75 ms 9664 KB Output is correct
12 Correct 81 ms 9620 KB Output is correct
13 Correct 74 ms 9784 KB Output is correct
14 Correct 70 ms 9604 KB Output is correct
15 Correct 71 ms 9540 KB Output is correct
16 Correct 852 ms 67212 KB Output is correct
17 Correct 574 ms 66812 KB Output is correct
18 Correct 729 ms 67048 KB Output is correct
19 Correct 649 ms 66492 KB Output is correct
20 Correct 828 ms 66204 KB Output is correct
21 Correct 857 ms 68744 KB Output is correct
22 Correct 846 ms 68220 KB Output is correct
23 Correct 842 ms 69076 KB Output is correct
24 Correct 834 ms 68372 KB Output is correct
25 Correct 796 ms 67476 KB Output is correct