#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define CDIV(a,b) (((a)+(b)-(1))/(b))
using ll = long long;
using ld = long double;
const ll inf = 1e9 + 37;
const ll mod = 1e9 + 7;
const ll N = 5e5 + 37;
const ld eps = 1e-9;
const ld PI = acos((ld)-1);
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct SegmentTree
{
int t[2 * N] = {};
int n = -37;
SegmentTree(int sz) : n(sz) {
}
void update(int idx, int val) {
for(t[idx += n] = val; idx > 1; idx >>= 1) {
t[idx >> 1] = max(t[idx], t[idx ^ 1]);
}
}
int query(int l, int r) {
int ans = -inf;
for(l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if(l & 1) {
ans = max(ans, t[l++]);
}
if(!(r & 1)) {
ans = max(ans, t[r--]);
}
}
return ans;
}
};
inline void solve(){
int n;
string s;
cin >> n >> s;
vector<int> norm(n + 1), rev(n + 1);
SegmentTree normal_tree(n), rev_tree(n);
for(int i = 0; i < n; ++i) {
norm[i + 1] = norm[i] + (s[i] == 'C' ? -1 : +1);
normal_tree.update(i + 1, norm[i + 1]);
}
reverse(s.begin(), s.end());
for(int i = 0; i < n; ++i) {
rev[i + 1] = rev[i] + (s[i] == 'C' ? -1 : +1);
rev_tree.update(i + 1, rev[i + 1]);
}
// cout << norm << endl << rev << endl;
int Q;
cin >> Q;
while(Q--) {
int l, r;
cin >> l >> r;
int nans = normal_tree.query(l, r) - norm[l - 1];
int rans = rev_tree.query(n - r + 1, n - l + 1) - rev[n - r];
cout << max({0, nans, rans}) << endl;
}
}
signed main(){
std::ios_base::sync_with_stdio(0);
std::cin.tie(NULL);
// signed t; cin >> t; while(t--)
solve();
}
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for(T& x : v)
is >> x;
return is;
}
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
os << "[";
for(size_t i = 0; i + 1 < N; ++i) {
os << a[i] << ", ";
}
if(N > 0)
os << a[N - 1];
os << "]";
return os;
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
os << "(" << p.first << ", " << p.second << ") ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
os << '[';
for(auto x : v)
os << x << ", ";
os << "] ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
