oj.uz

Submission #159101

# Submission time Handle Problem Language Result Execution time Memory
159101 2019-10-20T18:31:58 Z a_player Election (BOI18_election) C++14
0 / 100
 10 ms 632 KB 
#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.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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