Submission #151857

#	Time	Username	Problem	Language	Result	Execution time	Memory
151857		Knps4422	Election (BOI18_election)	C++14	0 / 100	4 ms	504 KiB

election

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, q;
int s[500005];
int st1[2000005],st2[2000005];
int p1[500005],p2[500005];
vector <int> vec;
void build1(int nod , int l , int r){
    if(l == r){
        st1[nod] = p1[l];
    }else{
        int mid = (l+r)/2;
        build1(nod*2,l,mid);
        build1(nod*2+1,mid+1,r);
        st1[nod] = max(st1[nod*2],st1[nod*2+1]);
    }
}
void build2(int nod , int l , int r){
    if(l == r){
        st2[nod] = p2[l];
    }else{
        int mid = (l+r)/2;
        build2(nod*2,l,mid);
        build2(nod*2+1,mid+1,r);
        st2[nod] = max(st2[nod*2],st2[nod*2+1]);
    }
}
void update1(int nod , int l , int r , int pos , int val){
    if(l > r)return ;
    if(pos <= r && pos >= l){
            st1[nod] = max(st1[nod],val);
            int mid = (l+r)/2;
            update1(2*nod  ,l    ,mid,pos,val);
            update1(2*nod+1,mid+1,r  ,pos,val);
    }
    return ;
}
int query1(int nod , int l , int r , int lt , int rt){
    if(l > r)return 0;
    if(l >= lt && r <= rt)return st1[nod];
    int mid = (l+r)/2;
    return max(query1(nod*2,l,mid,lt,rt),query1(nod*2+1,mid+1,r,lt,rt));
}
void update2(int nod , int l , int r , int pos , int val){
    if(l > r)return ;
    if(pos <= r && pos >= l){
            st2[nod] = max(st2[nod],val);
    }else{
        return ;
    }
    int mid = (l+r)/2;
    update2(2*nod,l,mid,pos,val);
    update2(2*nod+1,mid+1,r,pos,val);
}
int query2(int nod , int l , int r , int lt , int rt){
    if(l > r)return 0;
    if(l >= lt && r <= rt)return st2[nod];
    int mid = (l+r)/2;
    return max(query2(nod*2,l,mid,lt,rt),query2(nod*2+1,mid+1,r,lt,rt));
}
int main(){
    cin >> n;
    for(int i = 1; i <= n ; i++){
        char ch;
        cin >> ch;
        if(ch == 'C')s[i]=-1;
        else s[i]=1;
    }
    for(int i = 1; i <= 4*n ; i++){
        st1[i] = -1e9;
        st2[i] = -1e9;
    }
    int sum = 0;
    for(int i = 1 ; i <= n; i++){
        sum += s[i];
        p1[i] = sum;
    }
    build1(1,1,n);
    sum = 0;
    for(int i = n ; i > 0; i--){
        sum += s[i];
        p2[i]=sum;
    }
    build2(1,1,n);
    cin >> q;
    int li, ri;
    for(int i = 1 ;i <= q ;i++){
        cin >> li >> ri;
        int v1 = query1(1,li,ri,1,n);
        int v2 = query2(1,li,ri,1,n);
        vec.pb(max(0,max(v1 - p1[li-1],v2-p2[ri+1])));
    }
    for(auto i : vec){
        cout << i << '\n';
    }
    return 0;
}

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