Submission #128186

#	Time	Username	Problem	Language	Result	Execution time	Memory
128186		thanos	Election (BOI18_election)	C++14	28 / 100	3024 ms	2316 KiB

election

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
struct query{
  int l;
  int r;
}q[500005];
string A;
int main(){
  //freopen("1-elections.in","r",stdin);
  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 d=0; d<K; d++){
    bool v[100005]={false};
    int sum=0,cnt=0;
    for(int i=q[d].l; i<=q[d].r; i++){
      if(A[i-1]=='C'){
        sum--;
      }
      else{
        sum++;
      }
      if(sum>0 && A[i-1]=='T'){
        cnt++;
        v[i]=true;
        sum--;
      }
    }
    sum=0;
    for(int i=q[d].r; i>=q[d].l; i--){
      if(A[i-1]=='C'){
        sum--;
      }
      else{
        sum++;
      }
      if(sum>0 && !v[i] && A[i-1]=='T'){
        cnt++;
      }
      if((sum>0 && A[i-1]=='T') || v[i]) sum--;
    }
      cout<<cnt<<endl;
  }
  return 0;
}

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