//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int inf = 1e9 + 7;
struct SEGT{
vector < pair < int , int > > tree;
vector < int > lzt;
int tree_size;
bool is_inverse = 0;
SEGT(int x , bool bl){
tree_size = x + 3;
tree.assign(4 * tree_size , {0,inf});
lzt.assign(4 * tree_size , 0);
is_inverse = bl;
build(1,0,tree_size);
}
void build(int ind , int l , int r){
if(l == r){
tree[ind].second = l * (is_inverse ? -1 : 1);
return;
}
int mid = (l + r) >> 1;
build(ind*2 , l , mid);
build(ind*2+1 , mid+1 , r);
tree[ind].second = tree[ind*2].second;
}
void push(int ind , int l , int r){
if(lzt[ind] != 0){
tree[ind].first += lzt[ind];
if(l != r){
lzt[ind*2] += lzt[ind];
lzt[ind*2 + 1] += lzt[ind];
}
lzt[ind] = 0;
}
}
void update(int ind , int l , int r, int ql , int qr , int qv){
push(ind,l,r);
if(l >= ql and r <= qr){
lzt[ind] += qv;
push(ind,l,r);
return;
}
else if(l > qr or r < ql){
return;
}
else{
int mid = (l + r) >> 1;
update(ind*2 , l , mid , ql , qr , qv);
update(ind*2+1 , mid+1 , r , ql , qr , qv);
tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
}
}
void update(int l , int r , int v){
update(1,0,tree_size,l,r,v);
}
pair < int , int > query(int ind , int l , int r , int ql , int qr){
push(ind,l,r);
if(l >= ql and r <= qr){
return tree[ind];
}
else if(l > qr or r < ql){
return {inf,inf};
}
else{
int mid = (l + r) >> 1;
return min(query(ind*2 , l , mid , ql , qr) , query(ind*2+1 , mid+1 , r , ql , qr));
}
}
pair < int , int > query(int l , int r){
auto ret = query(1,0,tree_size,l,r);
ret.second *= is_inverse ? -1 : 1;
return ret;
}
};
void solve(){
int n;
cin >> n;
string str;
cin >> str;
SEGT prefix(n,0) , suffix(n,1);
int cur_sum = 0;
for(int i = 0;i<n;i++){
if(str[i] == 'C')cur_sum++;
else cur_sum--;
prefix.update(i+1 , i+1 , cur_sum);
}
cur_sum = 0;
for(int i = n-1;i>=0;i--){
if(str[i] == 'C')cur_sum++;
else cur_sum--;
suffix.update(i+1 , i+1 , cur_sum);
}
// cout << "pre : ";for(int i = 0;i<=12;i++)cout << prefix.query(i,i).first << " ";cout << endl;
// cout << "suf : ";for(int i = 0;i<=12;i++)cout << suffix.query(i,i).first << " ";cout << endl;
int q;
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
int tmp1 = -prefix.query(l-1,l-1).first , tmp2 = -suffix.query(r+1,r+1).first;
prefix.update(l,r,tmp1);
suffix.update(l,r,tmp2);
// cout << "pre : ";for(int i = 0;i<=12;i++)cout << prefix.query(i,i).first << " ";cout << endl;
// cout << "suf : ";for(int i = 0;i<=12;i++)cout << suffix.query(i,i).first << " ";cout << endl;
//updates
pair < int , int > qp = prefix.query(l,r) , qs = suffix.query(l,r);
int local_ans = max(0,-qp.first) + max(0,-qs.first);
int intersect = 0;
if(qp.second >= qs.second){
intersect = max(0,-qp.first) - max(0 , -prefix.query(qs.first , qs.first).first);
}
// cout << "local_ans : " << local_ans << endl;
// cout << "intersect : " << intersect << endl;
cout << local_ans - intersect << endl;
//redo the updates
prefix.update(l,r,-tmp1);
suffix.update(l,r,-tmp2);
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
