#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int q;
string s;
vector<int> psums;
const int MAXJ = 20;
vector<int> jumpmin[MAXJ];
vector<int> jumpmax[MAXJ];
const int INF = 1000000000;
void init(){
for(int b = 0; b < MAXJ; b++){
jumpmin[b].resize(psums.size());
jumpmax[b].resize(psums.size());
if(b == 0){
for(int i = 0; i < psums.size(); i++){
jumpmax[b][i] = jumpmin[b][i] = psums[i];
}
} else {
for(int i = 0; i + (1<<b) <= psums.size(); i++){
jumpmax[b][i] = max(jumpmax[b-1][i], jumpmin[b-1][i + (1<<(b-1))]);
jumpmin[b][i] = min(jumpmin[b-1][i], jumpmin[b-1][i + (1<<(b-1))]);
}
}
}
}
int range_max(int a, int b){
b++;
int c = 31 - __builtin_clz(b-a);
assert(c < MAXJ);
return max(jumpmax[c][a], jumpmax[c][b-(1<<c)]);
}
int range_min(int a, int b){
b++;
int c = 31 - __builtin_clz(b-a);
return min(jumpmin[c][a], jumpmin[c][b-(1<<c)]);
}
map<pair<int,int>, int> memo;
// [a,b] in [l,r]
int max_psum(int a, int b, int l, int r);
int get(int a, int b, int l, int r){
if(memo.find({a,b}) == memo.end()){
memo[{a,b}] = max_psum(a, b, l, r);
}
return memo[{a,b}];
}
int max_psum(int a, int b, int l, int r){
if(a == b || b <= l || r <= a) return 0;
int m = (l + r) / 2;
if(m == l){
return max(0, psums[b] - psums[a]);
}
if(b <= m){
return max_psum(a, b, l, m);
}
if(m <= a){
return max_psum(a, b, m, r);
}
int ans = 0;
ans = max(ans, get(a, m, l, m));
ans = max(ans, get(m, b, m, r));
ans = max(ans, range_max(m, b) - range_min(a, m));
return ans;
}
int max_psum_first(int a, int b){
return max_psum(a, b, 0, n);
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> n >> s >> q;
psums.push_back(0);
for(int i = 0; i < s.size(); i++){
if(s[i] == 'C'){
psums.push_back(psums[psums.size() - 1] + 1);
} else {
psums.push_back(psums[psums.size() - 1] - 1);
}
}
init();
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
l--; r--;
r++;
int a = max_psum_first(l, r);
cout << a - (psums[r] - psums[l]) << '\n';
}
}
Compilation message
election.cpp: In function 'void init()':
election.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < psums.size(); i++){
~~^~~~~~~~~~~~~~
election.cpp:25:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i + (1<<b) <= psums.size(); i++){
~~~~~~~~~~~^~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
