#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
const int len = 5e5+5, inf = 1e9;
int out[len], tree[4*len], lazy[4*len], pref[len], arr[len];
ii ask[len];
char str[len];
vector<int> st, vec[len];
void build(int p, int l, int r){
if (l == r)
tree[p] = pref[l], lazy[p] = 0;
else{
int mid = (l+r)/2;
build(2*p, l, mid);
build(2*p+1, mid+1, r);
tree[p] = min(tree[2*p], tree[2*p+1]);
lazy[p] = 0;
}
}
void prop(int p, int l, int r){
if (lazy[p] == 0) return;
tree[p] += lazy[p];
if (l != r){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
}
lazy[p] = 0;
}
void update(int p, int l, int r, int i, int j, int v){
prop(p, l, r);
if (i <= l && r <= j)
lazy[p] += v;
else if (r < i || j < l)
return;
else{
int mid = (l+r)/2;
update(2*p, l, mid, i, j, v);
update(2*p+1, mid+1, r, i, j, v);
prop(2*p, l, mid);
prop(2*p+1, mid+1, r);
tree[p] = min(tree[2*p], tree[2*p+1]);
}
}
int query(int p, int l, int r, int i, int j){
prop(p, l, r);
if (i <= l && r <= j)
return tree[p];
if (r < i || j < l)
return inf;
int mid = (l+r)/2;
return min(query(2*p, l, mid, i, j), query(2*p+1, mid+1, r, i, j));
}
int bs(int x){
int l = 0, r = (int)st.size()-1, ans = 0;
while (l <= r){
int mid = (l+r)/2;
if (st[mid] >= x)
ans = mid, r = mid-1;
else
l = mid+1;
}
return ans;
}
int main(){
int n, q;
scanf("%d %s", &n, &str);
for (int i = 1; i <= n; i++){
if (str[i-1] == 'C') arr[i] = 1;
else arr[i] = -1;
pref[i] = pref[i-1] + arr[i];
}
build(1, 1, n);
scanf("%d", &q);
for (int i = 0; i < q; i++){
scanf("%d %d", &ask[i].fi, &ask[i].se);
vec[ask[i].se].pb(i);
}
for (int i = 1; i <= n; i++){
if (arr[i] == 1 && !st.empty()){
update(1, 1, n, st.back(), n, -1);
st.pop_back();
}
if (arr[i] == -1){
update(1, 1, n, i, n, +1);
st.pb(i);
}
for (int j = 0; j < vec[i].size(); j++){
int l = ask[vec[i][j]].fi, r = i, lef = bs(l), rig = st.size()-lef;
//printf("l = %d, r = %d, lef = %d, rig = %d\n", l, r, lef, rig);
//printf("mn = %d\n", query(1, 1, n, l, r) - pref[l-1]);
out[vec[i][j]] = rig - min(0, query(1, 1, n, l, r)-pref[l-1]-lef);
}
}
for (int i = 0; i < q; i++)
printf("%d\n", out[i]);
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:82:28: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[500005]' [-Wformat=]
scanf("%d %s", &n, &str);
~~~~^
election.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec[i].size(); j++){
~~^~~~~~~~~~~~~~~
election.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %s", &n, &str);
~~~~~^~~~~~~~~~~~~~~~~~~
election.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
election.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ask[i].fi, &ask[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
