oj.uz

Submission #869246

# Submission time Handle Problem Language Result Execution time Memory
869246 2023-11-03T17:21:34 Z sofija6 Election (BOI18_election) C++14
100 / 100
 511 ms 48304 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
using namespace std;
ll n,a[MAXN],sz;
struct element
{
    ll pref=0,suff=0,sum=0,minn;
};
element Merge(element x,element y)
{
    element z;
    z.pref=min(x.pref,x.sum+y.pref);
    z.suff=min(y.suff,x.suff+y.sum);
    z.sum=x.sum+y.sum;
    z.minn=min({0ll,x.pref+y.suff,x.minn+y.sum,x.sum+y.minn});
    return z;
}
element neutral_element;
struct seg_tree
{
    vector<element> st;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Build()
    {
        for (ll i=sz;i<sz+n;i++)
            st[i]={min(0ll,a[i-sz+1]),min(0ll,a[i-sz+1]),a[i-sz+1],min(0ll,a[i-sz+1])};
        for (ll i=sz-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return neutral_element;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll q,l,r;
    string s;
    cin >> n >> s;
    for (ll i=0;i<n;i++)
        a[i+1]=(s[i]=='T')?-1 : 1;
    S.Init();
    S.Build();
    cin >> q;
    while (q--)
    {
        cin >> l >> r;
        element ans=S.Calc(l,r,1,1,sz);
        cout << abs(ans.minn) << "\n";
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 65 ms 12152 KB Output is correct
7 Correct 48 ms 11984 KB Output is correct
8 Correct 47 ms 12116 KB Output is correct
9 Correct 49 ms 12116 KB Output is correct
10 Correct 56 ms 12124 KB Output is correct
11 Correct 50 ms 12216 KB Output is correct
12 Correct 50 ms 12112 KB Output is correct
13 Correct 49 ms 12324 KB Output is correct
14 Correct 49 ms 12176 KB Output is correct
15 Correct 48 ms 12116 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 65 ms 12152 KB Output is correct
7 Correct 48 ms 11984 KB Output is correct
8 Correct 47 ms 12116 KB Output is correct
9 Correct 49 ms 12116 KB Output is correct
10 Correct 56 ms 12124 KB Output is correct
11 Correct 50 ms 12216 KB Output is correct
12 Correct 50 ms 12112 KB Output is correct
13 Correct 49 ms 12324 KB Output is correct
14 Correct 49 ms 12176 KB Output is correct
15 Correct 48 ms 12116 KB Output is correct
16 Correct 470 ms 47432 KB Output is correct
17 Correct 388 ms 47116 KB Output is correct
18 Correct 462 ms 47352 KB Output is correct
19 Correct 374 ms 46784 KB Output is correct
20 Correct 508 ms 46564 KB Output is correct
21 Correct 511 ms 48140 KB Output is correct
22 Correct 468 ms 48180 KB Output is correct
23 Correct 470 ms 48304 KB Output is correct
24 Correct 468 ms 48100 KB Output is correct
25 Correct 509 ms 47672 KB Output is correct