#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 1e9+7,inf = 1e9+10,base = 233;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k >>= 1;
}
return z;
}
int ps[N],cal[N];
bool go[N];
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
int n,q;
string s;
cin >> n >> s >> q;
s = '#'+s;
rep(i,1,n+1){
if (s[i] == 'C') ps[i] = ps[i-1]+1;
else ps[i] = ps[i-1]-1;
}
while (q--){
int l,r;
cin >> l >> r;
cal[l-1] = 0;
int mx = 0;
rep(i,l,r+1){
go[i] = 0;
if (ps[l-1]-ps[i] > mx || i == l) go[i] = 1;
mx = max(mx,ps[l-1]-ps[i]);
cal[i] = mx;
}
int ans = 0;
mx = 0;
repr(i,r,l){
mx = max(mx,-ps[r]+ps[i-1]);
if (!go[i]) continue;
ans = max(ans,mx+cal[i-1]);
}
cout << ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
