#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lli;
typedef long double lld;
typedef priority_queue <lli , vector<lli>, greater<lli> > min_heap;
typedef priority_queue <lli> max_heap;
typedef pair<lli, lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const lli M = 1e9 + 7;
const lli M1 = 0;
const lli M2 = 1000000000000000001;
lli mod(lli x){ return (x%M);}
lli mod_minus(lli a, lli b){ lli ans= (mod(a)-mod(b)); if(ans<0) ans=mod(ans+M); return ans;}
lli mod_mul(lli a,lli b){ return mod(mod(a)*mod(b));}
lli mod_add(lli a,lli b){ return mod(mod(a)+mod(b));}
#define FOR(i,l,u) for(int i=l;i<=u;i++)
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
#define All(A) A.begin(),A.end()
#define isPowerOfTwo(x) (x && (!(x&(x-1))))
#define LSOne(S) (S & (-S))
#define set_count(i) __builtin_popcount(i)
lli gcd(lli a, lli b) { return b == 0 ? a : gcd(b, a % b); }
lli lcm(lli a, lli b) { return a * (b / gcd(a, b)); }
lli phi(lli n) {
lli result = n;
for (lli i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
lli ceill(lli a,lli b)
{
if(a%b==0)
return a/b;
else
return a/b +1;
}
lli extendted_gcd(lli a ,lli b,lli &x,lli &y){
if(a==0){
x=0;y=1;return b;}
lli x1,y1,ans = extendted_gcd(b%a,a,x1,y1);
x = y1-(b/a)*x1;y = x1;
return ans;
}
lli power_mod(lli a,lli b,lli m)
{
lli ans =1;
while(b!=0)
{
if(b%2==1)
ans=(ans*a)%m;
a=a*a;
a%=m;
b/=2;
}
return ans;
}
lli mod_inverse(lli a,lli m)
{
return power_mod(a,m-2,m);
}
void mod_inverse_array(lli inv[],lli u,lli m)
{
inv[1]=1;
FOR(i,2,u){
inv[i]=((-(m/i)*inv[m%i]%m)+m)%m;
}
}
lli N_C_r_mod_m(lli N,lli r , vector<lli> factorial)
{
lli a = factorial[N],b = mod_inverse(factorial[N-r],M),c = mod_inverse(factorial[r],M);
return mod_mul(a,mod_mul(b,c));
}
void prime_factorization(lli n,unordered_map<lli,lli> &m)
{
lli i=2;
while(n%i==0)
{
m[i]++;
n=n/i;
}
for(i=3;i*i<=n;i+=2)
{
while(n%i==0)
{
m[i]++;
n=n/i;
}
}
if(n!=1)
m[n]++;
}
void linear_sieve(vector<lli> &pr,vector<lli> &lp,lli N)
{
for (lli i=2; i<=N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back (i);
}
for (lli j=0; j<(lli)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
lp[i * pr[j]] = pr[j];
}
}
lli eval_poly(vector<lli> coeff , lli x){
lli degree = coeff.size(); //coeff are as 0,1,2----n
degree--;
lli ans = 0;
for(lli i = degree ; i>=0 ; i--){
ans = (x*ans + coeff[i]);
}
return ans;
}
lli derivative_poly(vector<lli> coeff , lli x){
lli degree = coeff.size(); //coeff are as 0,1,2----n
degree--;
lli ans = 0;
lli pow = 1;
for(lli i = 1; i<=degree;i++){
ans+=(i*pow*coeff[i]);
pow*=x;
}
return ans;
}
int t = 1;
int n;
string s;
struct item{
int mp,ms,pi,si;
};
int sizer = 1;
vector<item> values;
vector<int> pre , suff;
item single(int pre , int suff , int i){
return {pre,suff,i,i};
}
item merge(item a, item b){
return {
mp : max(a.mp , b.mp),
ms : max(a.ms, b.ms),
pi : ((a.mp > b.mp) ? a.pi : b.pi),
si : ((a.ms > b.ms) ? a.si : b.si)
};
}
void build(int x = 0 , int lx = 0 , int rx = sizer){
if((rx - lx )<=1){
if(lx < s.size()){
values[x] = single(pre[lx], suff[lx],lx);
}
else{
values[x] = single(INT_MIN,INT_MIN , -1);
}
return;
}
int m = lx + (rx - lx)/2;
build(2*x + 1, lx , m);
build(2*x + 2, m , rx);
values[x] = merge(values[2*x + 1], values[2*x + 2]);
}
item query(int l , int r ,int x = 0 , int lx = 0 , int rx =sizer){
if(lx>=r || rx<=l) return single(INT_MIN,INT_MIN,-1);
if(lx>=l && rx<=r) return values[x];
int m = lx + (rx - lx)/2;
item r1 = query(l,r,2*x + 1, lx , m);
item r2 = query(l , r,2*x + 2, m , rx);
return merge(r1 , r2);
}
void solve(){
cin>>n;cin>>s;
while(sizer <n) sizer *=2;
values.resize(2*sizer);
pre.resize(n); suff.resize(n);
FOR(i,0,n-1){
pre[i] = (i >0 ? pre[i-1]:0) + (s[i] == 'C' ? -1 : 1);
}
for(int i = n-1 ; i>=0 ; i--){
suff[i] = (i<(n-1) ? suff[i+1] : 0) + (s[i] == 'C' ? -1 : 1);
}
build();
int m ; cin>>m;
FOR(i,1,m){
int left ,right ; cin>>left>>right;
left--;
item r = query(left,right);
int common = (r.pi>=r.si) ? (pre[r.pi] - ((r.si > 0 ) ?pre[r.si - 1] : 0)): 0;
int mp = r.mp - ((left > 0) ?pre[left - 1] : 0);
int ms = r.ms - ((right < n-1) ? suff[right] : 0);
// cout<<mp<<" "<<ms<<" "<<(min(common , min(mp,ms)))<<" ";
cout<<(mp + ms - min(common , min(mp,ms)))<<"\n";
}
}
int main()
{
FAST;
// g++ -o output prac.cpp
// .\output
// cin>>t;
// freopen("optmilk.in","r",stdin);
// freopen("optmilk.out","w",stdout);
while(t--){
solve();
}
return 0;
}
Compilation message
election.cpp: In function 'void build(int, int, int)':
election.cpp:169:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | if(lx < s.size()){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
