Submission #688981

#	Time	Username	Problem	Language	Result	Execution time	Memory
688981		EthanKim8683	Election (BOI18_election)	C++17	0 / 100	5 ms	408 KiB

election

#include<bits/stdc++.h>
using namespace std;
using I=int;
using C=char;
const I N=500000;
C fans[N];
pair<I,I>segs1[2*N];
pair<I,I>segs2[2*N];
I n;
pair<I,I>cmb1(pair<I,I>a,pair<I,I>b){
  auto[ic1,it1]=a;auto[ic2,it2]=b;
  return{ic1+ic2-min(ic1,it2),it1+it2-min(ic1,it2)};
}
pair<I,I>cmb2(pair<I,I>a,pair<I,I>b){
  auto[dc1,dt1]=a;auto[dc2,dt2]=b;
  return{dc1+dc2-min(dt1,dc2),dt1+dt2-min(dt1,dc2)};
}
void asn1(I i){
  segs1[i+n].first++,segs2[i+n].first++;
}
void asn2(I i){
  segs1[i+n].second++,segs2[i+n].second++;
}
void bld(){
  for(I i=n-1;i>0;i--)segs1[i]=cmb1(segs1[i<<1],segs1[i<<1|1]);
  for(I i=n-1;i>0;i--)segs2[i]=cmb2(segs2[i<<1],segs2[i<<1|1]);
}
I qry1(I l,I r){
  pair<I,I>lrs={0,0},rrs={0,0};
  for(l+=n,r+=n;l<r;l>>=1,r>>=1){
    if(l&1)lrs=cmb1(lrs,segs1[l++]);
    if(r&1)rrs=cmb1(segs1[--r],rrs);
  }
  return cmb1(lrs,rrs).second;
}
I qry2(I l,I r){
  pair<I,I>lrs={0,0},rrs={0,0};
  for(l+=n,r+=n;l<r;l>>=1,r>>=1){
    if(l&1)lrs=cmb2(lrs,segs2[l++]);
    if(r&1)rrs=cmb2(segs2[--r],rrs);
  }
  return cmb2(lrs,rrs).second;
}
I fnd1(I x,I y){
  I l=x,r=y+1;
  while(l<r){
    I m=l+(r-l)/2;
    qry1(x,m)>=qry1(x,y+1)?r=m:l=m+1;
  }
  return l;
}
I fnd2(I x,I y){
  I l=x,r=y+1;
  while(l<r){
    I m=l+(r-l+1)/2;
    qry2(m,y+1)>=qry2(x,y+1)?l=m:r=m-1;
  }
  return l;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>n;
  cin>>fans;
  for(I i=0;i<n;i++)fans[i]=='C'?asn1(i):asn2(i);
  bld();
  I q;cin>>q;
  while(q--){
    I l,r;cin>>l>>r,l--,r--;
    I x=fnd1(l,r),y=fnd2(l,r);
    printf("%i\n",qry1(l,r+1)+qry2(l,r+1)-min(qry1(l,r+1)-qry1(l,y),qry2(l,r+1)-qry2(x,r+1)));
  }
}

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