oj.uz

Submission #433767

# Submission time Handle Problem Language Result Execution time Memory
433767 2021-06-20T10:35:05 Z AmineTrabelsi Election (BOI18_election) C++14
0 / 100
 12 ms 332 KB 
#include "bits/stdc++.h"
using namespace std;
// Hi 

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--,r--;
        vector<int> type;
        vector<int> cnt;
        type.push_back((s[l] == 'C' ? 0 : 1));
        int curr = 1;
        for(int i=l+1;i<=r;i++){
            if(s[i] != s[i-1]){
                type.push_back(!type.back());
                cnt.push_back(curr);
                curr = 1;
            }else{
                curr++;
            }
        }
        cnt.push_back(curr);
        int x = cnt.size();
        vector<int> pref(x+1,0);
        int cnt_t = 0;
        int zer = 0;
        for(int i=x-1;i>=0;i--){
            if(type[i] == 0){
                zer += cnt[i];
            }else{
                if(cnt_t+cnt[i] > zer){
                    pref[i] = cnt_t+cnt[i]-zer;
                    cnt_t += cnt[i]-pref[i];
                }
            }
        }
        cnt_t = 0;
        zer = 0;
        int ans = 0;
        for(int i=0;i<x;i++){
            if(type[i] == 0){
                zer += cnt[i];
            }else{
                if(cnt_t+cnt[i] > zer){
                    pref[i] = max(pref[i],cnt_t+cnt[i]-zer);
                    ans += pref[i];
                    cnt_t += cnt[i]-pref[i];
                }else{
                    ans += pref[i];
                }
            }
        }
        cout << ans <<'\n';
    }
    return 0;
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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