Submission #137578

#	Time	Username	Problem	Language	Result	Execution time	Memory
137578		mlyean00	Election (BOI18_election)	C++14	28 / 100	3044 ms	1984 KiB

election

#ifdef DEBUG
#include "debug.hpp"
#else
#pragma GCC optimize("Ofast")
#define trace(...)
#include <bits/stdc++.h>
#define endl '\n'
#endif

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    string s;
    cin >> n >> s;

    vector<int> v(n);
    transform(s.begin(), s.end(), v.begin(),
              [](char c) { return c == 'C' ? 1 : -1; });

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        vector<bool> nullify(n);
        int ans = 0;
        {
            int s = 0;
            for (int i = l; i <= r; ++i) {
                if (s + v[i] < 0) {
                    nullify[i] = true;
                    ++ans;
                }
                s = max(0, s + v[i]);
            }
        }
        {
            int s = 0;
            for (int i = r; i >= l; --i) {
                if (nullify[i]) continue;
                if (s + v[i] < 0) {
                    nullify[i] = true;
                    ++ans;
                }
                s = max(0, s + v[i]);
            }
        }

        cout << ans << endl;
    }

    return 0;
}

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