Submission #1099575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099575		DangKhoizzzz	Election (BOI18_election)	C++14	0 / 100	1 ms	348 KiB

election

#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
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18