oj.uz

Submission #130611

# Submission time Handle Problem Language Result Execution time Memory
130611 2019-07-15T18:02:05 Z Vardanyan Election (BOI18_election) C++14
0 / 100
 21 ms 376 KB 
//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
int a[N];
int b[N];
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s = "0"+s;
    for(int i = 1;i<=n;i++){
        a[i] = a[i-1];
        if(s[i] == 'C') a[i]++;
        else a[i]--;
    }
    for(int i = n;i>=1;i--){
        b[i] = b[i+1];
        if(s[i] == 'C') b[i]++;
        else b[i]--;
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int mn = 0;
        int id = -1;
        int ans = 0;
        for(int i = l;i<=r;i++){
            if(a[i]<mn){
                mn = a[i];
                id = i;
            }
        }
        mn-=a[l-1];
        ans = max(ans,-mn);
        int qan = 0;
        for(int i = id;i>=1;i--){
           // if(qan >= -mn) break;
            if(s[i] == 'T' && qan<(-mn)){
                qan++;
            }
            b[i]+=qan;
        }

        int mnn = 1000*1000*1000+5;
        for(int i = l;i<=r;i++){
            if(b[i]<mnn){
                mnn = b[i];
            }
        }
        mnn-=b[r+1];
       if(mnn<=0) ans += (-mnn);
        qan = 0;
        for(int i = id;i>=1;i--){
           // if(qan>=-mn) break;
            if(s[i] == 'T' && qan<(-mn)){
                qan++;
            }
            b[i]-=qan;
        }
        cout<<ans<<endl;
    }

    return 0;
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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