Submission #378448

#	Time	Username	Problem	Language	Result	Execution time	Memory
378448		thecodingwizard	Election (BOI18_election)	C++11	0 / 100	6 ms	364 KiB

election

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

int cLeft[500001], cRight[500002], tLeft[500001], tRight[500002];

int main() {
    cin.tie(0)->sync_with_stdio(0);

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

    F0R(i, n) {
        cLeft[i+1] = cLeft[i] + (s[i] == 'C');
        tLeft[i+1] = tLeft[i] + (s[i] == 'T');
    }
    for (int i = n-1; ~i; i--) {
        cRight[i+1] = cRight[i+2] + (s[i] == 'C');
        tRight[i+1] = tRight[i+2] + (s[i] == 'T');
    }
    tRight[0] = tRight[1];
    cRight[0] = cRight[1];

    int q; cin >> q;
    F0R(i, q) {
        int L, R; cin >> L >> R;
        int l = L, r = R;
        int best = 0;
        while (l <= r) {
            int mid = (l+r)/2;
            int cl = cLeft[mid] - cLeft[L-1], cr = cRight[mid+1] - cRight[R+1];
            int tl = tLeft[mid] - tLeft[L-1], tr = tRight[mid+1] - tRight[R+1];
            int lft = min(cl, tl);
            int rht = min(cr, tr);
            best = max(best, min(lft, rht));
            if (lft > rht) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        best = tLeft[R] - tLeft[L-1] - best;
        cout << best << endl;
    }

    return 0;
}

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