#pragma GCC optimize ("O3")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
// author: amin_2008
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piii pair<pii, int>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvpii vector<vpii>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define ins insert
#define ts to_string
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define ld long double
#define ull unsigned long long
#define endl '\n'
#define int ll
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 2e5 * 1e9;
const int mod = 1e9+7;
const int sz = 5e5+5;
const int N = 1000003;
const int logg = 18;
const int P = 40000005;
const ll M = 8e5+5;
struct Node
{
int sum, pref, suff, res;
};
int n, a[sz];
struct SegmentTree
{
vector<Node> st;
SegmentTree(int n)
{
st.resize(n << 2);
}
Node merge(Node a, Node b)
{
return {a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum),
max({0LL, a.pref + b.suff, a.res, b.res, a.res + b.sum})};
}
void build(int l, int r, int in)
{
if (l == r)
{
st[in] = { a[l], max(0LL, a[l]), max(0LL, a[l]), max(a[l], 0LL) };
return;
}
int mid = (l + r) >> 1;
build(l, mid, in << 1);
build(mid + 1, r, in << 1 | 1);
st[in] = merge(st[in << 1], st[in << 1 | 1]);
}
Node get(int a, int b, int l, int r, int in)
{
if (l > b || r < a) return {0, 0, 0, 0};
if (a <= l && r <= b) return st[in];
int mid = (l + r) >> 1;
return merge(get(a, b, l, mid, in << 1), get(a, b, mid + 1, r, in << 1 | 1));
}
} st(sz);
void solve()
{
string s;
cin >> n >> s;
for (int i = 0; i < n; i++)
a[i] = (s[i] == 'C' ? -1 : 1);
st.build(0, n - 1, 1);
int q;
cin >> q;
while (q--)
{
int x, y;
cin >> x >> y;
Node result = st.get(--x, --y, 0, n - 1, 1);
cout << result.res << endl;
}
}
signed main()
{
ios;
//precompute();
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
63068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
63068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
63068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
