Submission #735781

#	Time	Username	Problem	Language	Result	Execution time	Memory
735781		GrindMachine	Election (BOI18_election)	C++17	100 / 100	508 ms	52964 KiB

election

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://github.com/stefdasca/CompetitiveProgramming/blob/master/BalkanOI/Balkan%2018-Election.cpp


let a[i] = 1 for 'C' and a[i] = -1 for 'T'

if only pref condition is there, then following greedy works:
iterate from l to r, add a[i] to sum
if sum < 0, then ignore curr guy and make sum = 0
add 1 to ans every time this op is done

how to handle suff cond?
first run pref, and find out the guys to ignore
when doing for pref, we make ignore ops as much to the right as possible
so when doing suff ops, this means ignore ops will come earlier
which will benefit the suff

so in short:
run pref, mark guys to ignore
run suff, ignore marked guys and ignore any addl guys if required

how to optimize?

if we can find out all guys ignored in the pref run, then we know the #of ops for the suff run
ops for suff run = -(min suff)

how to find and upd guys ignored in the pref run?

sweepline idea
sweep over l from n to 1

based on the value of a[l] (-1/1), upd the ignored guys
to find min suff after updates, use segtree

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll mnsuff, sum;
    };

    data neutral = {0, 0};

    data merge(data &left, data &right) {
        data curr;

        curr.mnsuff = min(right.mnsuff, right.sum + left.mnsuff);
        curr.sum = left.sum + right.sum;

        return curr;
    }

    void create(int i, T v) {
        tr[i] = {min(v, 0ll), v};
    }

    void modify(int i, T v) {
        tr[i] = {min(v, 0ll), v};
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n + 5);
    rep1(i, n) {
        char ch; cin >> ch;
        if (ch == 'C') a[i] = 1;
        else a[i] = -1;
    }

    ll q; cin >> q;
    vector<pll> here[n + 5];

    rep1(i, q) {
        ll l, r; cin >> l >> r;
        here[l].pb({r, i});
    }

    segtree<ll> st(n + 5);
    st.build(a, n + 1);

    deque<ll> dq;
    vector<ll> ans(q + 5);

    rev(l, n, 1) {
        if (a[l] == -1) {
            dq.push_front(l);
            st.pupd(l, 0);
        }
        else {
            if (!dq.empty()) {
                ll i = dq.front();
                st.pupd(i, -1);
                dq.pop_front();
            }
        }

        for (auto [r, id] : here[l]) {
            ll pref_ignored = upper_bound(all(dq), r) - dq.begin();
            ll suff_ignored = -st.query(l, r).mnsuff;
            ans[id] = pref_ignored + suff_ignored;
        }
    }

    rep1(i, q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

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