oj.uz

Submission #127634

# Submission time Handle Problem Language Result Execution time Memory
127634 2019-07-09T18:39:32 Z thanos Election (BOI18_election) C++14
0 / 100
 11 ms 504 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -