Submission #735775

#	Time	Username	Problem	Language	Result	Execution time	Memory
735775		GrindMachine	Election (BOI18_election)	C++17	28 / 100	3051 ms	1652 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


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

*/

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

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;

    while (q--) {
        ll l, r; cin >> l >> r;
        auto b = a;

        ll sum = 0;
        ll ans = 0;

        for (int i = l; i <= r; ++i) {
            sum += b[i];
            if (sum < 0) {
                ans++;
                sum = 0;
                b[i] = 0;
            }
        }

        sum = 0;

        rev(i, r, l) {
            sum += b[i];
            if (sum < 0) {
                ans++;
                sum = 0;
                b[i] = 0;
            }
        }

        cout << ans << endl;
    }
}

int main()
{
    fastio;

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

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

    return 0;
}

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