Submission #237591

#	Time	Username	Problem	Language	Result	Execution time	Memory
237591		Sorting	Election (BOI18_election)	C++14	0 / 100	10 ms	384 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int mx_N = 5e5 + 3;

int n, q;
string s;

int a[mx_N], cnt_prefix[mx_N];

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

    cin >> n >> s;

    for(int i = 0; i < n; ++i)
        a[i + 1] = (s[i] == 'C') ? 1 : -1;

    for(int i = 1; i <= n; ++i)
        cnt_prefix[i] = (a[i] == 1) + cnt_prefix[i - 1];

    cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;

        vector<int> v;
        int sum, curr, answer = 0;

        curr = 0, sum = 0;
        for(int j = l; j <= r; ++j){
            if(a[j] == -1 && !sum)
                curr++;
            else
                sum += a[j];
        }
        answer = max(answer, curr);

        curr = 0, sum = 0;
        for(int j = r; j >= l; --j){
            if(a[j] == -1 && !sum)
                curr++;
            else
                sum += a[j];
        }
        answer = max(answer, curr);

        cout << answer << "\n";
    }
}

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