Submission #237452

#	Time	Username	Problem	Language	Result	Execution time	Memory
237452		Sorting	Election (BOI18_election)	C++14	0 / 100	8 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 get_count(int l, int r){
    return cnt_prefix[r] - cnt_prefix[l - 1];
}

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 = 0, answer = (r - l + 1) - get_count(l, r);
        //cout << answer << " answer in beginning\n";
        int expected = 0;
        for(int j = l; j <= r; ++j){
            if(a[j] == 1) sum++;
            else{
                if(sum >= 1 && get_count(j + 1, r) >= expected + 1){
                    answer--;
                    sum--;
                    expected++;
                }
            }
        }

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

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