#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n;
string str;
int main(){
cin>>n>>str;
int lp[n][2], rp[n][2];
memset(lp, 0, sizeof(lp));
memset(rp, 0, sizeof(rp));
for(int i = 0; i < n; i++){
if(i == 0){
lp[0][1] = (str[i] == 'C');
lp[0][0] = (str[i] == 'T');
}
else{
lp[i][1] = lp[i-1][1] + (str[i] == 'C');
lp[i][0] = lp[i-1][0] + (str[i] == 'T');
}
//cout<<lp[i][0]<<" "<<lp[i][1]<<endl;
}
for(int i = str.size()-1; i >= 0; i--){
if(i == str.size()-1){
rp[i][1] = (str[i] == 'C');
rp[i][0] = (str[i] == 'T');
}
else{
rp[i][1] = rp[i+1][1] + (str[i] == 'C');
rp[i][0] = rp[i+1][0] + (str[i] == 'T');
}
}
int q;
cin>>q;
while(q--)
{
int a, b;
cin>>a>>b;
a--; b--;
int removeC = 0, removeT = 0;
if(a > 0)
removeC = lp[a-1][1], removeT = lp[a-1][0];
int lp_min = 1e9, rp_min = 1e9;
for(int i = a; i<= b; i++){
int curC = lp[i][1] - removeC, curT = lp[i][0] - removeT;
int keep = curC - curT;
lp_min = min(lp_min, keep);
}
removeC = 0;
removeT = 0;
if(b < n-1)
removeC = rp[b+1][1], removeT = rp[b+1][0];
for(int i = a; i<= b; i++){
int curC = rp[i][1] - removeC, curT = rp[i][0] - removeT;
// cout<<curC<<" "<<curT<<" "<<removeC<<" "<<removeT<<endl;
int keep = curC - curT;
rp_min = min(rp_min, keep);
}
cout<<-min(rp_min,lp_min)<<endl;
}
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if(i == str.size()-1){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
