oj.uz

Submission #59717

# Submission time Handle Problem Language Result Execution time Memory
59717 2018-07-23T00:35:30 Z model_code Election (BOI18_election) C++17
28 / 100
 3000 ms 1348 KB 
// 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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 248 KB Output is correct
2 Correct 14 ms 356 KB Output is correct
3 Correct 15 ms 424 KB Output is correct
4 Correct 16 ms 424 KB Output is correct
5 Correct 12 ms 496 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 248 KB Output is correct
2 Correct 14 ms 356 KB Output is correct
3 Correct 15 ms 424 KB Output is correct
4 Correct 16 ms 424 KB Output is correct
5 Correct 12 ms 496 KB Output is correct
6 Execution timed out 3031 ms 1348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 248 KB Output is correct
2 Correct 14 ms 356 KB Output is correct
3 Correct 15 ms 424 KB Output is correct
4 Correct 16 ms 424 KB Output is correct
5 Correct 12 ms 496 KB Output is correct
6 Execution timed out 3031 ms 1348 KB Time limit exceeded
7 Halted 0 ms 0 KB -