oj.uz

Submission #378750

# Submission time Handle Problem Language Result Execution time Memory
378750 2021-03-17T03:46:55 Z thecodingwizard Election (BOI18_election) C++11
28 / 100
 3000 ms 2656 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];

struct BIT {
    int n;
    vector<int> A;
    void init(int _n) {
        n = _n;
        A.assign(n+10, 0);
    }
    int qry(int x) {
        int s = 0;
        while (x) {
            s += A[x];
            x -= x&-x;
        }
        return s;
    }
    void upd(int k, int v) {
        while (k <= n) {
            A[k] += v;
            k += k&-k;
        }
    }
} matched;

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');
    }
    matched.init(n);

    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;
    stack<int> stuff;
    int tCtr = 0, maxT = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'C') {
            stuff.push(i);
            tCtr = max(tCtr-1, 0);
        } else {
            if (!stuff.empty()) {
                matched.upd(stuff.top(), 1);
                stuff.pop();
                tCtr++;
                maxT = max(maxT, tCtr + (int)stuff.size());
            }
        }

        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());
                    }
                }
            }
            int subtract = max(0, maxT - (int)stuff.size());

            ans[queries[idx].s] = matched.qry(n) - matched.qry(queries[idx].f.f-1);
            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 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 9 ms 492 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 9 ms 492 KB Output is correct
6 Execution timed out 3066 ms 2656 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 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 9 ms 492 KB Output is correct
6 Execution timed out 3066 ms 2656 KB Time limit exceeded
7 Halted 0 ms 0 KB -