Submission #674478

#	Time	Username	Problem	Language	Result	Execution time	Memory
674478		Samrev	Election (BOI18_election)	C++14	0 / 100	1 ms	340 KiB

election

#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);
        int res = mp + ms - min(common , min(mp,ms));
        cout<<max(res , 0)<<"\n";

    }

}
    

int main()
{
 
    FAST;
    // g++ -o output prac.cpp
    // .\output
    // cin>>t;

    // freopen("elections.in","r",stdin);
	// freopen("elections.out","w",stdout);
    while(t--){
        solve();

    }
    return 0;
 
}

Compilation message (stderr)

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()){
      |            ~~~^~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18