Submission #414216

#	Time	Username	Problem	Language	Result	Execution time	Memory
414216		shivensinha4	Election (BOI18_election)	C++17	100 / 100	1624 ms	57308 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

struct Node {
    int pref = 0, sum = 0;
};

class SegmentTree {
private:
    vector<Node> tree; int n;
    Node bound = {0, 0};

    static Node merge(Node a, Node b) {
        Node ans;
        ans.sum = a.sum + b.sum;
        ans.pref = max(a.pref, a.sum + b.pref);
        return ans;
    }

    void update(int i, int val, int l, int r, int p) {
        if (l > i or r < i) return;
        if (l == r) {
            tree[p] = {val, val};
            return;
        }

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
        tree[p] = merge(tree[c1], tree[c2]);
    }

    Node mx(int i, int j, int l, int r, int p) {
        if (l > j or r < i) return bound;
        if (l >= i and r <= j) return tree[p];

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        return merge(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
    }

public:
    SegmentTree(int _n) {
        n = _n;
        tree.resize(4*n, bound);
    }

    Node mx(int i, int j) {
        return mx(i, j, 0, n-1, 0);
    }

    void update(int i, int val) {
        update(i, val, 0, n-1, 0);
    }
};

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
private: vector<ll> tree; int n;
    int LSOne(int x) {
        return x&(-x);
    }

public:
    BIT(int x) {
        n = x;
        tree.resize(n+1);
    }
    ll sum(int a) {
        ll sum = 0;
        for (; a > 0; a -= LSOne(a)) sum += tree[a];
        return sum;
    }
    ll sum(int a, int b) {
        return sum(b) - (a == 1 ? 0 : sum(a-1));
    }
    void update(int p, ll v) {
        for (; p < n+1; p += LSOne(p)) tree[p] += v;
    }
};


int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vi nums(n);
    for_(i, 0, n) {
        char c; cin >> c;
        nums[i] = c == 'C' ? 1 : -1;
    }


    int q; cin >> q;
    vector<vector<ii>> ends(n);
    for_(i, 0, q) {
        int l, r; cin >> l >> r;
        ends[l-1].push_back({r-1, i});
    }

    vi out(q);
    stack<int> st;

    SegmentTree tree(n);
    BIT negpref(n);

    for (int i = n-1; i >= 0; i--) {
        if (nums[i] == -1) {
            negpref.update(i+1, 1);
            st.push(i);
        }
        else {
            tree.update(i, 1);
            if (st.size()) {
                negpref.update(st.top()+1, -1);
                tree.update(st.top(), -1);
                st.pop();
            }
        }

        for (auto &r: ends[i]) {
            Node temp = tree.mx(i, r[0]);
            out[r[1]] = temp.pref - temp.sum + negpref.sum(r[0]+1);
        }

    }

    for (auto i: out) cout << i << endl;
    cout << endl;
}

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