Submission #378742

#	Time	Username	Problem	Language	Result	Execution time	Memory
378742		thecodingwizard	Election (BOI18_election)	C++11	28 / 100	3085 ms	3296 KiB

election

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 500010

int ans[maxn];
int tPS[maxn];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    for (int i = 1; i <= n; i++) {
        tPS[i] = tPS[i-1] + (s[i] == 'T');
    }

    int q; cin >> q;
    vector<pair<ii, int>> queries;

    F0R(i, q) {
        int l, r; cin >> l >> r;
        queries.pb(mp(mp(l, r), i));
    }
    sort(all(queries), [](pair<ii, int> a, pair<ii, int> b) { return a.f.s < b.f.s; });

    int idx = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'C') {
        } else {
        }

        while (idx < q && queries[idx].f.s == i) {
            // process query idx

            stack<int> stuff;
            int tCtr = 0, maxT = 0;
            for (int i = queries[idx].f.f; i <= queries[idx].f.s; i++) {
                if (s[i] == 'C') {
                    stuff.push(i);
                    tCtr = max(tCtr-1, 0);
                } else {
                    if (!stuff.empty()) {
                        stuff.pop();
                        tCtr++;
                        maxT = max(maxT, tCtr + (int)stuff.size());
                        ans[queries[idx].s]++;
                    }
                }
            }
            int subtract = max(0, maxT - (int)stuff.size());

            //cout << subtract << endl;

            ans[queries[idx].s] -= subtract;
            ans[queries[idx].s] = tPS[queries[idx].f.s] - tPS[queries[idx].f.f-1] - ans[queries[idx].s];

            idx++;
        }
    }

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

    return 0;
}

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