Submission #750548

#	Time	Username	Problem	Language	Result	Execution time	Memory
750548		amin	Election (BOI18_election)	C++14	100 / 100	1189 ms	37808 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define ll long long
int sum[2500000];
int seg[2500000];
int segl[2500000];
int segr[2500000];
int a[2000000];
int z;
void merg(int v,int v1,int v2)
{

    sum[v]=sum[v1]+sum[v2];

    segl[v]=segl[v1]+max(0,segl[v2]-segl[v1]-sum[v1]);
    segr[v]=segr[v2]+max(0,segr[v1]-segr[v2]-sum[v2]);
   // segr[v]=max(segr[v1],segr[v2]);
    int add1=sum[v1]+segl[v1]+max(0,seg[v1]-segl[v1]-(sum[v2]+segr[v2]));
    seg[v]=segl[v1]+segr[v2]+max(0,seg[v1]-segl[v1]-(sum[v2]+segr[v2]))+max(0,seg[v2]-segr[v2]-add1);


}
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        if(a[tl]==1)
        {
        sum[v]=1;
        segl[v]=0;
        segr[v]=0;
        seg[v]=0;
        }else
        {
        sum[v]=-1;
        segl[v]=1;
        segr[v]=1;
        seg[v]=1;
        }
        return ;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    merg(v,v*2,v*2+1);
 //   cout<<tl<<' '<<tr<<' '<<seg[v]<<' '<<segl[v]<<' '<<segr[v]<<endl;
}
void ans(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return ;
    if(tl==l&&tr==r)
    {
      //   cout<<tl<<' '<<tr<<' '<<seg[z]<<endl;
        merg(z+1,z,v);
        seg[z]=seg[z+1];
        segl[z]=segl[z+1];
        segr[z]=segr[z+1];
        sum[z]=sum[z+1];
        // cout<<tl<<' '<<tr<<' '<<seg[z]<<endl;

        return ;
    }
    int tm=(tl+tr)/2;
    ans(v*2,tl,tm,l,min(r,tm));
    ans(v*2+1,tm+1,tr,max(l,tm+1),r);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  int n;
  cin>>n;
 char c[n];
 for(int i=0;i<n;i++)
 {
     cin>>c[i];
     if(c[i]=='T')
        a[i]=-1;
     else
        a[i]=1;
 }
 build(1,0,n-1);
 int q;
 cin>>q;
 while(q--)
 {
     int x,y;
     cin>>x>>y;
     x--;
     y--;
     z=n*4+1+q;

   seg[z+1]=  seg[z]=0;
   segl[z+1]=  segl[z]=0;
     segl[z+1]=segr[z]=0;
   sum[z+1]  =sum[z]=0;

ans(1,0,n-1,x,y);
     cout<<seg[z]<<endl;
 }

}

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