oj.uz

Submission #867566

# Submission time Handle Problem Language Result Execution time Memory
867566 2023-10-28T19:07:18 Z velislavgarkov Election (BOI18_election) C++14
0 / 100
 4 ms 2392 KB 
#include <iostream>
using namespace std;
const int MAXN=1e5+10;
int arr[MAXN], pref[MAXN], suf[MAXN];
int tree[4*MAXN][2];
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node][0]=pref[l];
        tree[node][1]=suf[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node][0]=min(tree[node*2][0],tree[node*2+1][0]);
    tree[node][1]=min(tree[node*2][1],tree[node*2+1][1]);
}
int query(int node, int l, int r, int ql, int qr, int ind) {
    if (ql>r || qr<l) return MAXN;
    if (l>=ql && r<=qr) return tree[node][ind];
    int mid=(l+r)/2;
    return min(query(node*2,l,mid,ql,qr,ind),query(node*2+1,mid+1,r,ql,qr,ind));
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    char ch;
    for (int i=1;i<=n;i++) {
        cin >> ch;
        if (ch=='C') arr[i]=1;
        else arr[i]=-1;
    }
    for (int i=1;i<=n;i++) pref[i]=pref[i-1]+arr[i];
    suf[n+1]=0;
    for (int i=n;i>=1;i--) suf[i]=suf[i+1]+arr[i];
    build_tree(1,1,n);
    int q, l, r;
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> l >> r;
        int s1=query(1,1,n,l,r,0)-pref[l-1];
        int s2=query(1,1,n,l,r,1)-suf[r+1];
        cout << max(0,-min(s1,s2)) << endl;   
    }
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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