Submission #127634

#	Time	Username	Problem	Language	Result	Execution time	Memory
127634		thanos	Election (BOI18_election)	C++14	0 / 100	11 ms	504 KiB

election

#include<iostream>
#include<string>
using namespace std;
int ll[500005],rr[500005];
struct query{
  int l;
  int r;
}q[500005],segtree[2000005];
void build(int node,int l,int r){
  if(l==r){
    segtree[node].l=ll[l]; //l and r are equal
    segtree[node].r=rr[r];
    return;
  }
  int mid=(l+r)/2;
  build(2*node,l,mid);
  build(2*node+1,mid+1,r);
  segtree[node].l=max(segtree[2*node].l,segtree[2*node+1].l);
  segtree[node].r=max(segtree[2*node].r,segtree[2*node+1].r);
  return;
}
int query(int node,int l,int r,int ql,int qr,char state){
  if(state=='l'){
    if(l>qr || r<ql){
      return 0;
    }
    if(ql<=l && r<=qr){
      return segtree[node].l;
    }
    int mid=(l+r)/2;
    return max(query(2*node,l,mid,ql,qr,state),query(2*node+1,mid+1,r,ql,qr,state));
  }
  else{
    if(l>qr || r<ql){
      return 0;
    }
    if(ql<=l && r<=qr){
      return segtree[node].r;
    }
    int mid=(l+r)/2;
    return max(query(2*node,l,mid,ql,qr,state),query(2*node+1,mid+1,r,ql,qr,state));
  }
}
string A;
int main(){
  int N;
  cin>>N;
  cin>>A;
  int K;
  cin>>K;
  for(int i=0; i<K; i++){
    cin>>q[i].l>>q[i].r;
  }
  for(int i=0; i<N; i++){
    if(A[i]=='C'){
      ll[i+1]=ll[i]-1;
    }
    else{
      ll[i+1]=ll[i]+1;
    }
  }
  for(int j=N-1; j>=0; j--){
    if(A[j]=='C'){
      rr[j+1]=rr[j+2]-1;
    }
    else{
      rr[j+1]=rr[j+2]+1;
    }
  }
  build(1,1,N);
  for(int i=0; i<K; i++){
    int a=query(1,1,N,q[i].l,q[i].r,'l');
    int b=query(1,1,N,q[i].l,q[i].r,'r');
    int dl=ll[q[i].l-1];
    int dr=rr[q[i].r+1];
    a-=dl; b-=dr;
    if(max(a,b)<=0){
      cout<<0<<endl;
    }
    else{
      cout<<max(a,b)<<endl;
    }
  }
  return 0;
}

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