#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e7;
const ll INFLL = 1e18;
const int MAX_N = 500000;
int N;
string str;
int Q;
bool chk[MAX_N+1];
int sum[MAX_N+1];
struct SEG{
struct NODE{
int l, r;
pii mx, mn;
};
vector<NODE> seg;
void add(){
seg.pb({-1, -1, {-MAX_N-1, 0}, {MAX_N+1, 0}});
}
int SZ;
void Init(int x){
SZ = x;
add();
init(0, 1, SZ);
}
void init(int idx, int s, int e){
if(s==e){
seg[idx].mx = {sum[s], s};
seg[idx].mn = {sum[s], s};
return;
}
seg[idx].l = seg.size(); add(); seg[idx].r = seg.size(); add();
init(seg[idx].l, s, (s+e)/2);
init(seg[idx].r, (s+e)/2+1, e);
seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
}
pii Mx(int x, int y){
return mx(0, 1, SZ, x, y);
}
pii mx(int idx, int s, int e, int x, int y){
if(x<=s && e<=y){
return seg[idx].mx;
}
if(x>e || y<s){
return {-INF, 0};
}
return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
}
pii Mn(int x, int y){
return mn(0, 1, SZ, x, y);
}
pii mn(int idx, int s, int e, int x, int y){
if(x<=s && e<=y){
return seg[idx].mn;
}
if(x>e || y<s){
return {INF, 0};
}
return min(mn(seg[idx].l, s, (s+e)/2, x, y), mn(seg[idx].r, (s+e)/2+1, e, x, y));
}
}Seg;
int main(){
cin>>N>>str>>Q;
for(int i=1; i<=N; i++){
sum[i] = sum[i-1];
if(str[i-1]=='C') sum[i]++;
else sum[i]--;
//cout<<sum[i]<<endl;
}
Seg.Init(N);
for(int i=0; i<Q; i++){
int a, b;
scanf("%d%d", &a, &b); a--;
int s = sum[a], e = sum[b];
pii mx = Seg.Mx(a+1, b), mn = Seg.Mn(a+1, b);
//cout<<mx.first<<" "<<mx.second<<" "<<mn.first<<" "<<mn.second<<endl;
if(mn.second<mx.second){
printf("%d\n", max(0, s-mn.first) + max(0, mx.first-e));
}else{
pii mx2 = Seg.Mx(mn.second, b), mn2 = Seg.Mn(a+1, mx.second);
mn2.first = min(mn2.first, s); mx2.first = max(mx2.first, e);
//cout<<mn2.first<<" "<<mx2.first<<endl;
printf("%d\n", s-mn2.first + mx2.first-e + max(mn2.first-mn.first, mx.first-mx2.first));
}
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); a--;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
