oj.uz

Submission #1101107

# Submission time Handle Problem Language Result Execution time Memory
1101107 2024-10-15T14:31:47 Z DangKhoizzzz Election (BOI18_election) C++14
100 / 100
 387 ms 30028 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pii;

const int maxn = 5e5 + 7;

struct node
{
    int pre , suf , sum , ans;
};

int n , a[maxn];

node st[maxn*4];

node merging(node Lnode , node Rnode)
{
    node res;

    res.sum = Lnode.sum + Rnode.sum;

    res.pre = max(Lnode.pre , Lnode.sum + Rnode.pre);
    res.suf = max(Rnode.suf , Lnode.suf + Rnode.sum);

    int ans1 = Lnode.ans + Rnode.sum;
    int ans2 = Rnode.ans + Lnode.sum;
    int ans3 = Lnode.pre + Rnode.suf;

    res.ans = max(ans1 , max(ans2 , ans3));

    return res;
}

void build(int id , int l , int r)
{
    if(l == r)
    {
        st[id].pre = st[id].suf = max(0 , a[l]);
        st[id].sum = a[l];
        st[id].ans = max(0 , a[l]);
        return;
    }
    int mid = (l+r)/2;

    build(id*2 , l , mid);
    build(id*2+1 , mid+1 , r);

    st[id] = merging(st[id*2] , st[id*2+1]);
}

node get(int id , int l , int r , int u , int v)
{
    if(r < u || l > v) return {0 , 0 , 0 , 0};

    if(u <= l && r <= v) return st[id];

    int mid = (l+r)/2;

    node Lnode = get(id*2 , l , mid , u , v);
    node Rnode = get(id*2+1 , mid+1 , r , u , v);

    return merging(Lnode , Rnode);
}


void solve()
{
    cin >> n ;

    for(int i = 1; i <= n; i++)
    {
        char ch; cin >> ch;

        if(ch == 'T') a[i] = 1;
        else a[i] = -1;
    }

    build(1 , 1, n);

    int q; cin >> q;

    while(q--)
    {
        int l , r;
        cin >> l >> r;

        cout << get(1 , 1, n , l , r).ans << '\n';
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 37 ms 7892 KB Output is correct
7 Correct 35 ms 7916 KB Output is correct
8 Correct 35 ms 7752 KB Output is correct
9 Correct 31 ms 7760 KB Output is correct
10 Correct 35 ms 7760 KB Output is correct
11 Correct 41 ms 8008 KB Output is correct
12 Correct 37 ms 7888 KB Output is correct
13 Correct 36 ms 8060 KB Output is correct
14 Correct 35 ms 8008 KB Output is correct
15 Correct 48 ms 8008 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 37 ms 7892 KB Output is correct
7 Correct 35 ms 7916 KB Output is correct
8 Correct 35 ms 7752 KB Output is correct
9 Correct 31 ms 7760 KB Output is correct
10 Correct 35 ms 7760 KB Output is correct
11 Correct 41 ms 8008 KB Output is correct
12 Correct 37 ms 7888 KB Output is correct
13 Correct 36 ms 8060 KB Output is correct
14 Correct 35 ms 8008 KB Output is correct
15 Correct 48 ms 8008 KB Output is correct
16 Correct 318 ms 28832 KB Output is correct
17 Correct 274 ms 28492 KB Output is correct
18 Correct 268 ms 28736 KB Output is correct
19 Correct 246 ms 28120 KB Output is correct
20 Correct 301 ms 27984 KB Output is correct
21 Correct 320 ms 29712 KB Output is correct
22 Correct 346 ms 29720 KB Output is correct
23 Correct 387 ms 30028 KB Output is correct
24 Correct 351 ms 29624 KB Output is correct
25 Correct 382 ms 28972 KB Output is correct