oj.uz

Submission #61456

# Submission time Handle Problem Language Result Execution time Memory
61456 2018-07-26T04:32:47 Z 노영훈(#1778) Election (BOI18_election) C++11
28 / 100
 3000 ms 1208 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n, q;
char S[MX];
int out[MX];
int solve(int l, int r, int idx){
    int res=0;
    for(int i=l, cnt=0; i<=r; i++){
        if(cnt==0 && S[i]=='T') out[i]=idx, res++;
        cnt += out[i]==idx ? 0 : S[i]=='T' ? 1 : -1;
    }
    for(int i=r, cnt=0; i>=l; i--){
        if(out[i]==idx) continue;
        if(cnt==0 && S[i]=='T')  out[i]=idx, res++;
        cnt += out[i]==idx ? 0 : S[i]=='T' ? 1 : -1;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>(S+1);
    cin>>q;
    for(int i=1; i<=q; i++){
        int l,r; cin>>l>>r;
        cout<<solve(l,r,i)<<'\n';
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 11 ms 556 KB Output is correct
3 Correct 9 ms 556 KB Output is correct
4 Correct 7 ms 568 KB Output is correct
5 Correct 7 ms 568 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 11 ms 556 KB Output is correct
3 Correct 9 ms 556 KB Output is correct
4 Correct 7 ms 568 KB Output is correct
5 Correct 7 ms 568 KB Output is correct
6 Execution timed out 3025 ms 1208 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 11 ms 556 KB Output is correct
3 Correct 9 ms 556 KB Output is correct
4 Correct 7 ms 568 KB Output is correct
5 Correct 7 ms 568 KB Output is correct
6 Execution timed out 3025 ms 1208 KB Time limit exceeded
7 Halted 0 ms 0 KB -