Submission #59717

#	Time	Username	Problem	Language	Result	Execution time	Memory
59717		model_code	Election (BOI18_election)	C++17	28 / 100	3031 ms	1348 KiB

election

// Andrei-Costin Constantinescu
// O(N^2)
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 500000 + 5;
int N, v[NMAX];

int main() {
    //freopen("data.in", "r", stdin);
    cin >> N;
    assert(1 <= N && N <= 500000);

    string votes;
    cin >> votes;
    assert(static_cast <int>(votes.size()) == N);

    for (int i = 1; i <= N; ++ i) {
        assert(votes[i - 1] == 'C' || votes[i - 1] == 'T');
        v[i] = votes[i - 1] == 'C' ? 1 : -1;
    }

    int Q = 0;
    cin >> Q;
    assert(1 <= Q && Q <= 500000);

    vector <int> marked;
    for (int i = 1; i <= Q; ++ i) {
        int l, r;
        cin >> l >> r;
        assert(1 <= l && l <= r && r <= N);

        marked.clear();
        int sum = 0, ans = 0;
        for (int j = l; j <= r; ++ j) {
            sum += v[j];
            if (sum < 0)
                sum = 0, ++ ans, marked.push_back(j);
        }

        sum = 0;
        for (int j = r, k = marked.size() - 1; j >= l; -- j) {
            while (k >= 0 && marked[k] > j)
                -- k;
            if (k >= 0 && marked[k] == j)
                continue;
            sum += v[j];
            if (sum < 0)
                sum = 0, ++ ans;
        }

        cout << ans << '\n';
    }
    return 0;
}

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