oj.uz

Submission #137578

# Submission time Handle Problem Language Result Execution time Memory
137578 2019-07-28T06:53:03 Z mlyean00 Election (BOI18_election) C++14
28 / 100
 3000 ms 1984 KB 
#ifdef DEBUG
#include "debug.hpp"
#else
#pragma GCC optimize("Ofast")
#define trace(...)
#include <bits/stdc++.h>
#define endl '\n'
#endif

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<int> v(n);
    transform(s.begin(), s.end(), v.begin(),
              [](char c) { return c == 'C' ? 1 : -1; });

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        vector<bool> nullify(n);
        int ans = 0;
        {
            int s = 0;
            for (int i = l; i <= r; ++i) {
                if (s + v[i] < 0) {
                    nullify[i] = true;
                    ++ans;
                }
                s = max(0, s + v[i]);
            }
        }
        {
            int s = 0;
            for (int i = r; i >= l; --i) {
                if (nullify[i]) continue;
                if (s + v[i] < 0) {
                    nullify[i] = true;
                    ++ans;
                }
                s = max(0, s + v[i]);
            }
        }

        cout << ans << endl;
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Execution timed out 3044 ms 1984 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Execution timed out 3044 ms 1984 KB Time limit exceeded
7 Halted 0 ms 0 KB -