Submission #1274199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274199		domi	Election (BOI18_election)	C++20	0 / 100	16 ms	31904 KiB

election

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e5;

using namespace std;

vector<pii>qu[NMAX + 5];
vector<int>stk;
char ch;
int a[NMAX + 5], ans[NMAX + 5], n, q;

///cate numere din stk sunt >= l
inline int cate(int l){
    if (stk.empty()) return 0;

    auto it = lower_bound(all(stk), l);
    return distance(it, stk.end());
}

struct Node{
    int sum;
    int min_suf;

    Node () : sum(0), min_suf(INT_MAX) {}

    Node (int x) : sum(x), min_suf(x) {}

    static Node merge(const Node& left, const Node& right){
        if (left.min_suf == INT_MAX) return right;
        if (right.min_suf == INT_MAX) return left;

        Node aux;
        aux.sum = left.sum + right.sum;
        aux.min_suf = min(right.min_suf, right.sum + left.min_suf);
        return aux;
    }

};

struct ST{

    Node aint[4 * NMAX + 5];

    void build(int nod = 1, int st = 1, int dr = n){
        if (st == dr){
            aint[nod] = Node(a[st]);
            return;
        }

        int m = (st + dr) >> 1;
        build(2 * nod, st, m);
        build(2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    void update(int pos, int val, int nod = 1, int st = 1, int dr = n){
        if (st == dr){
            aint[nod] = Node(val);
            return;
        }

        int m = (st + dr) >> 1;
        if (pos <= m)
            update(pos, val, 2 * nod, st, m);
        else
            update(pos, val, 2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    Node query(int l, int r, int nod = 1, int st = 1, int dr = n){
        if (st > r || dr < l) return Node();
        if (l <= st && dr <= r) return aint[nod];

        int m = (st + dr) >> 1;
        return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
     }


}aint;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; ++i){
        cin >> ch;
        a[i] = (ch == 'C' ? 1 : -1);
    }

    cin >> q;
    for (int i = 1, l, r; i <= q; ++i){
        cin >> l >> r;
        qu[r].push_back({l, i});
    }

    aint.build();
    for (int i = 1; i <= n; ++i){

        if (a[i] == -1) {
            aint.update(i, 0);
            stk.push_back(i);
        }

        if (a[i] == 1 && !stk.empty()) {
            aint.update(stk.back(), -1);
            stk.pop_back();
        }

        for (auto &[l, idx] : qu[i])
            ans[idx] = cate(l) + abs(min(0LL, aint.query(l, i).min_suf));
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
    return 0;
}

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