oj.uz

Submission #571488

# Submission time Handle Problem Language Result Execution time Memory
571488 2022-06-02T10:01:32 Z choigameautohackrb Election (BOI18_election) C++17
28 / 100
 3000 ms 2216 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+7;
ll n, Q, a[N], b[N], l, r;
char s;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        a[i]=(s=='C')?1:-1;
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>l>>r;
        ll sum=0,countb=0;
        for(int pos=l;pos<=r;pos++){
            b[pos]=0;
            sum+=a[pos];
            if(sum<0){
                b[pos]--;
                sum=0;
                countb++;
            }
        }
        sum=0;
        for(int pos=r;pos>=l;pos--){
            sum+=a[pos];
            if(sum<0){
                b[pos]++;
                sum=0;
            }
        }
        sum=0;
        for(int pos=l;pos<=r;pos++){
            sum+=b[pos];
            if(sum<0) sum=0;
        }
        cout<<countb+sum<<'\n';
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 8 ms 392 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 8 ms 392 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Execution timed out 3044 ms 2216 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 8 ms 392 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Execution timed out 3044 ms 2216 KB Time limit exceeded
7 Halted 0 ms 0 KB -