oj.uz

Submission #128186

# Submission time Handle Problem Language Result Execution time Memory
128186 2019-07-10T13:46:31 Z thanos Election (BOI18_election) C++14
28 / 100
 3000 ms 2316 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 632 KB Output is correct
2 Correct 28 ms 504 KB Output is correct
3 Correct 26 ms 504 KB Output is correct
4 Correct 27 ms 512 KB Output is correct
5 Correct 23 ms 504 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 632 KB Output is correct
2 Correct 28 ms 504 KB Output is correct
3 Correct 26 ms 504 KB Output is correct
4 Correct 27 ms 512 KB Output is correct
5 Correct 23 ms 504 KB Output is correct
6 Execution timed out 3024 ms 2316 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 632 KB Output is correct
2 Correct 28 ms 504 KB Output is correct
3 Correct 26 ms 504 KB Output is correct
4 Correct 27 ms 512 KB Output is correct
5 Correct 23 ms 504 KB Output is correct
6 Execution timed out 3024 ms 2316 KB Time limit exceeded
7 Halted 0 ms 0 KB -