oj.uz

Submission #942749

# Submission time Handle Problem Language Result Execution time Memory
942749 2024-03-11T03:53:53 Z irmuun Election (BOI18_election) C++17
100 / 100
 423 ms 74772 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct Info{
    ll pre=0,suf=0,sum=0,ans=0;
    Info(){*this=Info(0);}
    Info(ll x){
        pre=suf=ans=max(0ll,x);
        sum=x;
    }
};

Info operator+(Info l,Info r){
    Info res;
    res.pre=max(l.pre,l.sum+r.pre);
    res.suf=max(r.sum+l.suf,r.suf);
    res.sum=l.sum+r.sum;
    res.ans=max({l.ans+r.sum,l.sum+r.ans,l.pre+r.suf});
    return res;
}

struct segtree{
    ll n;
    string s;
    vector<Info>d;
    segtree(string str){
        s=str;
        n=s.size();
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            ll x=(s[l]=='T'?1:-1);
            d[node].pre=d[node].suf=d[node].ans=max(0ll,x);
            d[node].sum=x;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    Info query(ll node,ll l,ll r,ll L,ll R){
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        if(R<=mid){
            return query(node*2,l,mid,L,R);
        }
        if(mid+1<=L){
            return query(node*2+1,mid+1,r,L,R);
        }
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    segtree sg(s);
    ll q;
    cin>>q;
    while(q--){
        ll l,r;
        cin>>l>>r;
        l--,r--;
        cout<<sg.query(1,0,n-1,l,r).ans<<"\n";
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 36 ms 10488 KB Output is correct
7 Correct 46 ms 10620 KB Output is correct
8 Correct 42 ms 10752 KB Output is correct
9 Correct 29 ms 10492 KB Output is correct
10 Correct 36 ms 10324 KB Output is correct
11 Correct 36 ms 10584 KB Output is correct
12 Correct 37 ms 10576 KB Output is correct
13 Correct 37 ms 10580 KB Output is correct
14 Correct 47 ms 10892 KB Output is correct
15 Correct 37 ms 10588 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 36 ms 10488 KB Output is correct
7 Correct 46 ms 10620 KB Output is correct
8 Correct 42 ms 10752 KB Output is correct
9 Correct 29 ms 10492 KB Output is correct
10 Correct 36 ms 10324 KB Output is correct
11 Correct 36 ms 10584 KB Output is correct
12 Correct 37 ms 10576 KB Output is correct
13 Correct 37 ms 10580 KB Output is correct
14 Correct 47 ms 10892 KB Output is correct
15 Correct 37 ms 10588 KB Output is correct
16 Correct 423 ms 73636 KB Output is correct
17 Correct 304 ms 73312 KB Output is correct
18 Correct 333 ms 73464 KB Output is correct
19 Correct 275 ms 72948 KB Output is correct
20 Correct 420 ms 72952 KB Output is correct
21 Correct 380 ms 74492 KB Output is correct
22 Correct 392 ms 74560 KB Output is correct
23 Correct 370 ms 74772 KB Output is correct
24 Correct 398 ms 74360 KB Output is correct
25 Correct 389 ms 74036 KB Output is correct