oj.uz

Submission #783212

# Submission time Handle Problem Language Result Execution time Memory
783212 2023-07-14T17:56:09 Z Ahmed57 Election (BOI18_election) C++17
100 / 100
 799 ms 29712 KB 
#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,1,i+1,-1);
        }else update(1,1,n+1,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,1,idx+1,1);
                add(idx+1,1);
            }else{
                if(st.size()){
                    update(1,1,n+1,1,st.top()+1,-1);
                    add(st.top()+1,-1);
                    st.pop();
                }
            }
            idx--;
        }
        int ans = query(1,1,n+1,i.first.first+1,i.first.second+2);
        ans-=query(1,1,n+1,i.first.second+2,i.first.second+2);
        lol[i.second] = sum(i.first.second+1)-sum(i.first.first)+abs(ans);
    }
    for(int i = 1;i<=q;i++){
        cout<<lol[i]<<"\n";
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 472 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 472 KB Output is correct
6 Correct 95 ms 5364 KB Output is correct
7 Correct 96 ms 5324 KB Output is correct
8 Correct 87 ms 5364 KB Output is correct
9 Correct 83 ms 5376 KB Output is correct
10 Correct 87 ms 5444 KB Output is correct
11 Correct 99 ms 5380 KB Output is correct
12 Correct 94 ms 5476 KB Output is correct
13 Correct 89 ms 5388 KB Output is correct
14 Correct 90 ms 5376 KB Output is correct
15 Correct 85 ms 5392 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 472 KB Output is correct
6 Correct 95 ms 5364 KB Output is correct
7 Correct 96 ms 5324 KB Output is correct
8 Correct 87 ms 5364 KB Output is correct
9 Correct 83 ms 5376 KB Output is correct
10 Correct 87 ms 5444 KB Output is correct
11 Correct 99 ms 5380 KB Output is correct
12 Correct 94 ms 5476 KB Output is correct
13 Correct 89 ms 5388 KB Output is correct
14 Correct 90 ms 5376 KB Output is correct
15 Correct 85 ms 5392 KB Output is correct
16 Correct 780 ms 28608 KB Output is correct
17 Correct 723 ms 28076 KB Output is correct
18 Correct 757 ms 28444 KB Output is correct
19 Correct 693 ms 27908 KB Output is correct
20 Correct 747 ms 27660 KB Output is correct
21 Correct 781 ms 29712 KB Output is correct
22 Correct 799 ms 28624 KB Output is correct
23 Correct 773 ms 29556 KB Output is correct
24 Correct 752 ms 28536 KB Output is correct
25 Correct 696 ms 27592 KB Output is correct