#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
//using namespace atcoder
#define YES cout << "YES"
#define NO cout << "NO"
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vc vector<char>
#define vd vector<double>
#define vld vector<long double>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define f first
#define s second
#define pii pair<int , int>
#define pll pair<ll , ll>
#define pil pair<int , ll>
#define pli pair<ll , int>
#define psi pair<string , int>
#define pci pair<char , int>
#define pic pair<int , char>
#define pis pair<int , string>
#define psl pair<string , ll>
#define pcl pair<char , ll>
#define plc pair<ll , char>
#define pls pair<ll , string>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ins insert
#define END return 0
#define mod 1e9
#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) (x).begin() , (x).end()
#define oo 1e9
#define size(x) x.size()
/*
int gcd(int number1 , int number2){
if(number2 == 0){
return number1;
}
return gcd(number2 , number1 % number2);
}
int lcm(int number1 , int number2){
return number1 / gcd(number1 , number2) * number2;
}
ll fact(int number){
ll product = 1;
for(int i=2 ; i<=number ; i++){
product *= i;
}
return product;
}
*/
//#define int ll
void binary(int l , int r , string s , int num){
int L = 0 , R = num , best = num;
while(L <= R){
int mid = L + (R - L) / 2;
int numc = 0 , numt = 0 , flg1 = 1 , flg2 = 1;
for(int i=l ; i<=r ; i++){
if(s[i] == 'C'){
numc++;
}
else{
numt++;
}
if((numt - mid) > numc){
flg1 = 0;
break;
}
}
numc = 0 ; numt = 0;
for(int i=r ; i>=l ; i--){
if(s[i] == 'C'){
numc++;
}
else{
numt++;
}
if((numt - mid) > numc){
flg2 = 0;
break;
}
}
if(flg1 == 1 && flg2 == 1){
best = mid;
R = mid - 1;
}
else{
L = mid + 1;
}
}
cout << best << '\n';
}
void solve(){
int n;
cin >> n;
string s;
cin >> s;
int T;
cin >> T;
while(T--){
int l , r , num = 0;
cin >> l >> r; l--; r--;
for(int i=l ; i<=r ; i++){
if(s[i] == 'T'){
num++;
}
}
binary(l , r , s , num);
}
}
/*signed */ int main(){
speed;
int t = 1;
//cin >> t;
while(t--){
solve();
}
END;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
