Submission #867566

#	Time	Username	Problem	Language	Result	Execution time	Memory
867566		velislavgarkov	Election (BOI18_election)	C++14	0 / 100	4 ms	2392 KiB

election

#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
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18