#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
template<typename F>
void multitest(F func) {
int t;
cin >> t;
while(t--) func();
}
void report(int ok) {
cout << (ok?"YES":"NO") << '\n';
}
struct segtree {
struct node {
int mn, lazy;
node() : mn(0), lazy(0) {}
void apply(int x) {
mn += x, lazy += x;
}
void push(node &l, node &r) {
l.apply(lazy), r.apply(lazy), lazy = 0;
}
void build(node &l, node &r) {
mn = min(l.mn, r.mn);
assert(!lazy);
}
};
vector<node> st;
int n;
segtree(int n) : st(4*n), n(n) {}
void update(int v, int l, int r, int ql, int qr, int add) {
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) {
st[v].apply(add);
return;
}
st[v].push(st[2*v], st[2*v+1]);
int mid = (l+r)/2;
update(2*v, l, mid, ql, qr, add);
update(2*v+1, mid+1, r, ql, qr, add);
st[v].build(st[2*v], st[2*v+1]);
}
void update(int l, int r, int add) { return update(1, 1, n, l, r, add); }
int query(int v, int l, int r, int ql, int qr) {
if(qr < l || r < ql) return 1<<30;
if(ql <= l && r <= qr) return st[v].mn;
st[v].push(st[2*v], st[2*v+1]);
int mid = (l+r)/2;
return min(query(2*v, l, mid, ql, qr), query(2*v+1, mid+1, r, ql, qr));
}
int query(int l, int r) { return query(1, 1, n, l, r); }
};
int n, q, a[1<<20], pref[1<<20], ans[1<<20];
vector<array<int, 2>> todo[1<<20];
segtree st(0);
int main() {
cin.tie(0)->sync_with_stdio(0);
//multitest([&](){});
cin >> n;
st = segtree(n);
char c;
for(int i = 1; i <= n; i++) cin >> c, a[i] = c=='C'?1:-1, pref[i] = pref[i-1]+a[i];
cin >> q;
for(int l, r, i = 0; i < q; i++) {
cin >> l >> r;
todo[r].push_back({l, i});
}
vector<int> bad;
for(int i = 1; i <= n; i++) {
st.update(i, n, a[i]);
if(a[i] == 1 && bad.size()) {
st.update(bad.back(), n, -1);
bad.pop_back();
}
if(a[i] == -1) {
bad.push_back(i);
st.update(i, n, 1);
}
//for(auto i : bad) cout << i << " "; cout << endl;
for(auto [l, id] : todo[i]) {
int mn = st.query(l, i) - pref[l-1];
ans[id] = bad.end() - lower_bound(all(bad), l);
//cout << l << " ff " << ans[id] << endl;
ans[id] += max(0, -mn);
}
}
for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
