Submission #137593

#	Time	Username	Problem	Language	Result	Execution time	Memory
137593		mlyean00	Election (BOI18_election)	C++14	0 / 100	4 ms	376 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; });
    vector<int> pref(n + 1), suff(n + 1);
    partial_sum(v.begin(), v.end(), pref.begin() + 1);
    partial_sum(v.rbegin(), v.rend(), suff.rbegin() + 1);

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        int ans = 0;
        {
            int mn = INT_MAX;
            for (int i = l; i <= r; ++i) {
                mn = min(mn, pref[i + 1]);
            }
            ans = min(ans, mn - pref[l]);
        }
        {
            int mn = INT_MAX;
            for (int i = l; i <= r; ++i) {
                mn = min(mn, suff[i]);
            }
            ans = min(ans, mn - suff[r + 1]);
        }
        ans = -ans;
        cout << ans << endl;
    }

    return 0;
}

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