Submission #159101

#	Time	Username	Problem	Language	Result	Execution time	Memory
159101		a_player	Election (BOI18_election)	C++14	0 / 100	10 ms	632 KiB

election

#include <bits/stdc++.h>

using namespace std;


int v[500001];
int rmqs[500001][20];
int rmqr[500001][20];
int N,Q;
int main(){
  cin>>N;
  for(int i=1;i<=N;i++){
    char a;cin>>a;
    if(a=='C')v[i]=1;
    else v[i]=-1;
  }

  rmqs[0][0]=0;
  for(int i=1;i<=N;i++){
    rmqs[i][0]=rmqs[i-1][0]+v[i];

  }
  for(int j=1;(1<<j)<=N;j++){
  for(int i=0;i+(1<<j)-1<=N;i++){
    rmqs[i][j]=min(rmqs[i][j-1],rmqs[i+(1<<(j-1))][j-1]);

  }

}

  rmqr[0][0]=0;
  for(int i=1;i<=N;i++){
    rmqr[i][0]=rmqr[i-1][0]+v[N-i+1];

  }
  for(int j=1;(1<<j)<=N;j++)
  for(int i=0;i+(1<<j)-1<=N;i++){
    rmqr[i][j]=min(rmqr[i][j-1],rmqr[i+(1<<(j-1))][j-1]);
  }
cin>>Q;
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    int d=log2(b-a+1);
    int s=min(rmqs[a-1][d],rmqs[b-(1<<d)+1][d]);
    int r=min(rmqr[N-b][d],rmqr[N-a+1-(1<<d)+1][d]);
    cout<<max(rmqs[a-1][0]-s,rmqr[N-b][0]-r)<<endl;
  }
}

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