oj.uz

Submission #379300

# Submission time Handle Problem Language Result Execution time Memory
379300 2021-03-17T23:32:14 Z thecodingwizard Election (BOI18_election) C++11
0 / 100
 6 ms 492 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 maxPrefix[4*maxn], sum[4*maxn];

// first is sum, second is max prefix
ii qry(int p, int i, int j, int L, int R) {
    if (i > R || j < L) return mp(0, -inf);
    if (L <= i && j <= R) {
        return mp(sum[p], maxPrefix[p]);
    }
    ii lft = qry(p*2, i, (i+j)/2, L, R);
    ii rht = qry(p*2+1, (i+j)/2+1, j, L, R);
    return mp(lft.f + rht.f, max(lft.s, lft.f + rht.s));
}

void upd(int p, int i, int j, int k, int v) {
    if (i > k || j < k) return;
    if (i == j && j == k) {
        maxPrefix[p] = v;
        sum[p] = v;
        return;
    }
    upd(p*2, i, (i+j)/2, k, v);
    upd(p*2+1, (i+j)/2+1, j, k, v);
    maxPrefix[p] = max(maxPrefix[p*2], sum[p*2]+maxPrefix[p*2+1]);
    sum[p] = sum[p*2]+sum[p*2+1];
}

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

    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    for (int i = 1; i <= 4*n; i++) {
        maxPrefix[i] = 0; sum[i] = 0;
    }

    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> removedT;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'C') {
            upd(1, 1, n, i, -1);
            if (!removedT.empty()) {
                int tgt = removedT.top();
                upd(1, 1, n, tgt, 1);
                removedT.pop();
            }
        } else {
            removedT.push(i);
        }
        
        while (idx < q && queries[idx].f.s == i) {
            // process query idx
            int toRemove = removedT.size();

            int extraRemove = qry(1, 1, n, queries[idx].f.f, queries[idx].f.s).s;

            ans[queries[idx].s] = toRemove + max(extraRemove, 0);
            idx++;
        }
    }

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

    return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -