Submission #867582

#	Time	Username	Problem	Language	Result	Execution time	Memory
867582		velislavgarkov	Election (BOI18_election)	C++14	100 / 100	979 ms	29968 KiB

election

#include <iostream>
using namespace std;
const int MAXN=5e5+10;
struct Node {
    int sum;
    int minpr;
    int minsuf;
    int x;
};
int arr[MAXN];
Node tree[4*MAXN];
Node combine (Node a, Node b) {
    Node ans;
    ans.sum=a.sum+b.sum;
    ans.minpr=min(a.minpr,a.sum+b.minpr);
    ans.minsuf=min(b.minsuf,b.sum+a.minsuf);
    ans.x=min(a.minpr+b.minsuf,min(a.x+b.sum,b.x+a.sum));
    ans.x=min(0,ans.x);
    return ans;
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node]={arr[l],min(0,arr[l]),min(0,arr[l]),min(0,arr[l])};
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node]=combine(tree[node*2],tree[node*2+1]);
}
Node query(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return {0,0,0,0};
    if (l>=ql && r<=qr) return tree[node];
    int mid=(l+r)/2;
    return combine(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
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;
    }
    build_tree(1,1,n);
    int q, l, r;
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> l >> r;
        Node ans=query(1,1,n,l,r);
        cout << -ans.x << endl;
    }
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18