oj.uz

Submission #378742

# Submission time Handle Problem Language Result Execution time Memory
378742 2021-03-17T03:39:56 Z thecodingwizard Election (BOI18_election) C++11
28 / 100
 3000 ms 3296 KB 
#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

#define maxn 500010

int ans[maxn];
int tPS[maxn];

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

    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    for (int i = 1; i <= n; i++) {
        tPS[i] = tPS[i-1] + (s[i] == 'T');
    }

    int q; cin >> q;
    vector<pair<ii, int>> queries;

    F0R(i, q) {
        int l, r; cin >> l >> r;
        queries.pb(mp(mp(l, r), i));
    }
    sort(all(queries), [](pair<ii, int> a, pair<ii, int> b) { return a.f.s < b.f.s; });

    int idx = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'C') {
        } else {
        }

        while (idx < q && queries[idx].f.s == i) {
            // process query idx

            stack<int> stuff;
            int tCtr = 0, maxT = 0;
            for (int i = queries[idx].f.f; i <= queries[idx].f.s; i++) {
                if (s[i] == 'C') {
                    stuff.push(i);
                    tCtr = max(tCtr-1, 0);
                } else {
                    if (!stuff.empty()) {
                        stuff.pop();
                        tCtr++;
                        maxT = max(maxT, tCtr + (int)stuff.size());
                        ans[queries[idx].s]++;
                    }
                }
            }
            int subtract = max(0, maxT - (int)stuff.size());

            //cout << subtract << endl;

            ans[queries[idx].s] -= subtract;
            ans[queries[idx].s] = tPS[queries[idx].f.s] - tPS[queries[idx].f.f-1] - ans[queries[idx].s];

            idx++;
        }
    }

    F0R(i, q) cout << ans[i] << endl;

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 9 ms 492 KB Output is correct
4 Correct 8 ms 492 KB Output is correct
5 Correct 8 ms 492 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 9 ms 492 KB Output is correct
4 Correct 8 ms 492 KB Output is correct
5 Correct 8 ms 492 KB Output is correct
6 Execution timed out 3085 ms 3296 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 9 ms 492 KB Output is correct
4 Correct 8 ms 492 KB Output is correct
5 Correct 8 ms 492 KB Output is correct
6 Execution timed out 3085 ms 3296 KB Time limit exceeded
7 Halted 0 ms 0 KB -