#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ld long double
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 5000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , q , ps[maxn] , fen[maxn] , sp[maxn] , res;
pii seg[4 * maxn] , ges[4 * maxn] ;
string s ;
void add(int i){
for(i ++ ; i < maxn ; i += i & -i){
fen[i] ++ ;
}
}
int get(int i){
res = 0 ;
for(i ++ ; i ; i &= i-1 ) res += fen[i] ;
return res ;
}
int GET(int l , int r){
return get(r) - get(l-1) ;
}
void bld(int x = 1 , int lx = 1 , int rx = n + 1){
if(rx - lx == 1){
ges[x] = {sp[lx] , lx };
return ;
}
int mid = lx + rx >> 1 ;
bld(x << 1 , lx , mid) ;
bld(x << 1 | 1, mid , rx) ;
ges[x] = min(ges[x << 1] , ges[x << 1 | 1]) ;
}
pii getmn(int l , int r, int x = 1 , int lx = 1 , int rx = n + 1){
if(lx >= r || rx <= l ) return {mod , mod} ;
if(lx >= l && rx <= r){
return ges[x] ;
}
int mid = lx + rx >> 1 ;
return min(getmn(l , r , x << 1 , lx , mid) , getmn(l , r , x << 1 | 1 , mid , rx)) ;
}
void build(int x = 1, int lx = 1, int rx = n + 1){
if(rx - lx == 1){
seg[x] = {ps[lx] , -lx };
return ;
}
int mid = lx + rx >> 1 ;
build(x << 1 , lx , mid) ;
build(x << 1 | 1 , mid , rx) ;
seg[x] = min(seg[x << 1] , seg[x << 1 | 1]) ;
}
pii getmin(int l , int r , int x = 1 , int lx = 1 , int rx = n + 1){
if(lx >= r || rx <= l){
return {mod , mod} ;
}
if(lx >= l && rx <= r){
return seg[x] ;
}
int mid = lx + rx >> 1 ;
return min(getmin(l , r , x << 1 , lx , mid) , getmin(l , r, x << 1 | 1 , mid , rx)) ;
}
int main()
{
migmig ;
cin>>n>>s ;
s = '&'+s ;
for(int i = 1 ; i <= n ; i ++ ){
ps[i] = ps[i-1] + (s[i] == 'C' ? 1 : -1) ;
if(s[i] == 'T'){
add(i) ;
}
}
for(int i = n ; i >= 1 ; i-- ){
sp[i] = sp[i + 1] + (s[i] == 'C' ? 1 : -1) ;
}
cin>>q ;
int l , r , p1 , p2 , val ;
pii res1 , res2 ;
build() ;
bld() ;
while(q--){
cin>>l>>r ;
res1 = getmin(l , r + 1 ) ;
res2 = getmn(l , r + 1) ;
p1 = -1 * res1.Y ;
p2 = res2.Y ;
if(p1 >= p2){
val = GET(p2 , p1) ;
val = min(val , max( (ps[p1] - ps[l-1]) * -1 , (sp[p2] - sp[r + 1]) * -1 )) ;
}else{
val = 0 ;
}
// cout<<"p1 :" << p1 << " p2 :" << p2 <<" val :" << val << endl ;
cout<<val + max(0 , (ps[p1] - ps[l-1]) * -1 - val) + max(0 , (sp[p2] - sp[r + 1]) * -1 - val) << "\n" ;
}
}
Compilation message
election.cpp: In function 'void bld(int, int, int)':
election.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = lx + rx >> 1 ;
| ~~~^~~~
election.cpp: In function 'std::pair<int, int> getmn(int, int, int, int, int)':
election.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = lx + rx >> 1 ;
| ~~~^~~~
election.cpp: In function 'void build(int, int, int)':
election.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int mid = lx + rx >> 1 ;
| ~~~^~~~
election.cpp: In function 'std::pair<int, int> getmin(int, int, int, int, int)':
election.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = lx + rx >> 1 ;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
