oj.uz

Submission #1099575

# Submission time Handle Problem Language Result Execution time Memory
1099575 2024-10-11T16:50:57 Z DangKhoizzzz Election (BOI18_election) C++14
0 / 100
 1 ms 348 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 INF = 1e9;
const int maxn = 5e5 + 7;

int n, q, a[maxn], ps[maxn];

pii st[maxn*4];

void build(int id, int l, int r)
{
    if(l == r)
    {
        st[id].fi = st[id].se = ps[l];
        return;
    }

    int mid = (l+r)/2;

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

    st[id].fi = min(st[id*2].fi, st[id*2+1].fi);
    st[id].se = max(st[id*2].se, st[id*2+1].se);
}

pii getmm(int id, int l, int r, int u, int v)
{
    if(l > v || r < u) return {INF, -INF};

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

    int mid = (l+r)/2;

    pii Lget = getmm(id*2, l, mid, u, v);
    pii Rget = getmm(id*2+1, mid+1, r, u, v);

    return {min(Lget.fi, Rget.fi), max(Lget.se, Rget.se)};
}



void solve()
{
    cin >> n;

    string s;
    cin >> s;

    s = '@' + s;

    for(int i = 1; i <= n; i++)
    {
        int val = -1;

        if(s[i] == 'C') val = 1;

        ps[i] = ps[i-1] + val;
    }

    //for(int i = 1; i <= n; i++) cout << ps[i] << ' ';

    build(1, 0, n);

    cin >> q;

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

        int res = 0;
        int mn = getmm(1 , 0 , n , l , r).fi;
        int mx = getmm(1 , 0 , n , l-1 , r-1).se;

        if(mn < ps[l-1]) res = max(res, ps[l-1] - mn);
        if(mx > ps[r]) res = max(res, mx - ps[r]);

        cout << res << '\n';
    }
}


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

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -