Submission #783209

#	Time	Username	Problem	Language	Result	Execution time	Memory
783209		Ahmed57	Election (BOI18_election)	C++17	0 / 100	3 ms	596 KiB

election

#include<bits/stdc++.h>

using namespace std;
int seg[2000001],lazy[2000001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = 0;return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    seg[p] = 0;
}
void prop(int p,int l,int r){
    seg[p]+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return seg[p];
    if(l>rq||r<lq)return 1e9;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
//BIT Fenwick tree
int n ;
int bit[500001]={0};
void add(int e,int v){
    while(e<=n){
        bit[e]+=v;
        e+=e&-e;
    }
}
long long sum(int e){
    long long res = 0;
    while(e>=1){
        res+=bit[e];
        e -= e&-e;
    }
    return res;
}
//end BIT
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    string s;cin>>n>>s;
    build(1,1,n);
    for(int i = 0;i<n;i++){
        if(s[i]=='T'){
            update(1,1,n,1,i+1,-1);
        }else update(1,1,n,1,i+1,1);
    }
    int q;cin>>q;
    int lol[q+1] = {0};
    vector<pair<pair<int,int>,int>> qu;
    for(int i = 1;i<=q;i++){
        int l,r;cin>>l>>r;
        l--;r--;
        qu.push_back({{l,r},i});
    }
    sort(qu.begin(),qu.end());reverse(qu.begin(),qu.end());
    int idx = n-1;
    stack<int> st;
    for(auto i:qu){
        while(idx>=i.first.first){
            if(s[idx]=='T'){
                st.push(idx);
                update(1,1,n,1,idx+1,1);
                add(idx+1,1);
            }else{
                if(st.size()){
                    update(1,1,n,1,st.top()+1,-1);
                    add(st.top()+1,-1);
                    st.pop();
                }
            }
            idx--;
        }
        int ans = query(1,1,n,i.first.first+1,i.first.second+1);
        if(i.first.second+1<n){
            ans-=query(1,1,n,i.first.second+2,i.first.second+2);
        }
        lol[i.second] = sum(i.first.second+1)-sum(i.first.first)+min(0,abs(ans));
    }
    for(int i = 1;i<=q;i++){
        cout<<lol[i]<<"\n";
    }
    return 0;
}

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