#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool cmpup(pair<int,int> a, pair<int,int> b){
if(a.first == b.first)return a.second < b.second;
return a.first < b.first;
}
bool cmpdown(pair<int,int> a, pair<int,int> b){
if(a.first == b.first)return a.second > b.second;
return a.first < b.first;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int lg = 19;
int n;
cin>>n;
string s;
cin>>s;
vector<int> vals(n+1,0);
vector<vector<pair<int,int>>> sparseup(n+1, vector<pair<int,int>>(lg, {0,0}));
vector<vector<pair<int,int>>> sparsedown(n+1, vector<pair<int,int>>(lg, {0,0}));
vector<int> prefix0(n+1, 0);
for(int i =1; i<=n; i++){
prefix0[i] = prefix0[i-1];
if(s[i-1] == 'T')vals[i] = -1;
if(s[i-1] == 'T')prefix0[i]++;
if(s[i-1] == 'C')vals[i] = 1;
}
vector<int> prefixu(n+1, 0);
for(int i =1; i<=n; i++){
prefixu[i] = prefixu[i-1] + vals[i];
//cout<<prefixu[i]<<" ";
sparseup[i][0] = {prefixu[i], i};
}
vector<int> prefixd(n+2, 0);
for(int i =n; i>=1; i--){
prefixd[i] = prefixd[i+1] + vals[i];
sparsedown[i][0] = {prefixd[i], i};
}
//for(auto k : prefixd)cout<<k<<" ";
//cout<<"\n";
for(int j = 1; j<lg; j++){
for(int i = 1; i<= n - (1<<j)+1; i++){
bool first = cmpup(sparseup[i][j-1], sparseup[i + (1<<(j-1))][j-1]);
if(first)sparseup[i][j] = sparseup[i][j-1];
else sparseup[i][j] = sparseup[i + (1<<(j-1))][j-1];
}
}
for(int j = 1; j<lg; j++){
for(int i = 1; i<= n - (1<<j)+1; i++){
bool first = cmpdown(sparsedown[i][j-1], sparsedown[i + (1<<(j-1))][j-1]);
if(first)sparsedown[i][j] = sparsedown[i][j-1];
else sparsedown[i][j] = sparsedown[i + (1<<(j-1))][j-1];
}
}
//for(auto k : prefixu)cout<<k<<" ";
//cout<<"\n";
int q;
cin>>q;
for(int i =0; i<q; i++){
int x, y;
cin>>x>>y;
int start = prefixu[x-1];
int fin = prefixd[y+1];
pair<int,int> up;
pair<int,int> down;
int dif = y - x + 1;
int p2 = __lg(dif - 1);
bool f = cmpup(sparseup[x][p2], sparseup[y - (1<<p2) + 1][p2]);
if(f)up = sparseup[x][p2];
else up = sparseup[y - (1<<p2) + 1][p2];
f = cmpdown(sparsedown[x][p2], sparsedown[y - (1<<p2) + 1][p2]);
if(f) down = sparsedown[x][p2];
else down = sparsedown[y - (1<<p2) + 1][p2];
//cout<<up.second<<" "<<down.second<<" ";/////
if(up.second < down.second){
int sol = max(0, start - up.first);
sol += max(0, fin - down.first);
//cout<<sol<<"\n";
continue;
}
else{
int xx = down.second;
int yy = up.second;
int sol = 0;
int zeros = prefix0[yy] - prefix0[xx-1];
int ones = yy - xx + 1 - zeros;
xx--;
yy++;
if(xx >= x){
p2 = __lg(xx - x);
f = cmpup(sparseup[x][p2], sparseup[xx - (1<<p2)+1][p2]);
if(f)sol += max(0, start - sparseup[x][p2].first);
else sol += max(0, start - sparseup[xx - (1<<p2)+1][p2].first);
}
int addeda = sol;
//cout<<sol<<" ";
if(yy <= y){
p2 = __lg(y - yy);
f = cmpup(sparsedown[yy][p2], sparsedown[y - (1<<p2)+1][p2]);
//cout<<fin<<": "<<p2<<": ";
//if(f)cout<<":::";
if(f)sol += max(0, fin - sparsedown[yy][p2].first);
else sol += max(0, fin - sparsedown[y - (1<<p2)+1][p2].first);
}
int addedb = sol-addeda;
//cout<<sol<<" ";
//cout<<ones<<" "<<zeros<<" ";
yy--;
xx++;
int bonusa = prefixu[xx-1] - prefixu[x-1] + addeda;
bonusa = max(0, bonusa);
//cout<<yy+1<<" "<<y+1<<" ";
int bonusb = prefixd[yy+1] - prefixd[y+1] + addedb;
//cout<<"\n,,";
//cout<<prefixd[yy+1]<<" "<<prefixd[y+1]<<" ";
bonusb = max(0, bonusb);
int neg = zeros - ones;
//cout<<bonusa<<" "<<bonusb<<" "<<neg<<" ";
sol += max(0,max(neg - bonusa, neg - bonusb));
cout<<sol<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
