Submission #1267608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267608		Alebn	Election (BOI18_election)	C++20	28 / 100	3095 ms	1712 KiB

election

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

signed main() {
    int n, q, x, y;
    string s;
    cin >> n >> s;
    vector<int> a(n), pref(n);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'C') a[i] = 1;
        else a[i] = -1;
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
    }
    function<int(int,int)> sum = [&](int l, int r) {
        return pref[r] - (l ? pref[l - 1] : 0);
    };
    cin >> q;
    while(q--) {
        cin >> x >> y;
        x--, y--;
        int kak = sum(x, y);
        int l = abs(min(0LL, kak)), r = y - x + 2, mid, ans, add, cnt;
        bool ok;
        while(l <= r) {
            mid = (l + r) / 2, ok = true;
            // go through 
            add = 0, cnt = 0;
            for(int i = x; i <= y; i++) {
                if(sum(x, i) + add < 0) {
                    add++, cnt++;
                }
                if(sum(x, i) + add > kak + mid || cnt > mid) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                r = mid - 1;
                ans = mid;
            } else l = mid + 1;
        }
        cout << ans << "\n";
    }
}

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