Submission #996160

#	Time	Username	Problem	Language	Result	Execution time	Memory
996160		amine_aroua	Election (BOI18_election)	C++17	0 / 100	9 ms	29272 KiB

election

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
int n , q;
const int N = (1<<19);
struct segTree
{
    vector<int> tree;
    segTree(vector<int> &a)
    {
        tree.assign(2*N , N);
        fore(i , N)
        {
            tree[i + N] = a[i];
        }
        forn(i , N - 1 , 1)
            tree[i] = min(tree[2*i] , tree[2*i + 1]);
    }
    int query(int l , int r)
    {
        l+=N;
        r+=N;
        if(l == r)
            return tree[l];
        int lt = tree[l] , rt = tree[r];
        while(l + 1 < r) {
            if (l % 2 == 0)
                lt = min(lt, tree[l + 1]);
            if (r % 2 == 1)
                rt = min(tree[r - 1], rt);
            l>>=1;
            r>>=1;
        }
        return min(lt , rt);
    }
};
vector<int> a(N) , pref(N) , suf(N);
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    map<int , vector<int>>posPref , posSuf ;
    map<int ,vector<int>> pos;
    forr(i , 1 , n)
    {
        char c;
        cin>>c;
        if(c == 'C')
            a[i] = 1;
        else
            a[i] = -1;
        pos[a[i]].pb(i);
        pref[i] = a[i] + pref[i - 1];
        posPref[pref[i]].pb(i);
    }
    forn(i , n , 1)
    {
        suf[i] = suf[i + 1] + a[i];
    }
    forr(i , 1 , n)
        posSuf[suf[i]].pb(i);
    segTree pmin(pref) , smin(suf);
    cin>>q;
    while (q--)
    {
        int _l , _r;
        cin>>_l>>_r;
        if(pref[_r] - pref[_l - 1] == -(_r - _l + 1))
        {
            cout<<_r - _l + 1<<nl;
            continue;
        }
        int ans = 0;
        int l = *lower_bound(pos[1].begin() , pos[1].end() , _l);
        ans+=l - _l;
        int r = *prev(upper_bound(pos[1].begin() , pos[1].end() , _r));
        ans+=_r - r;
        int mp = pmin.query(l , r) - pref[l - 1];
        int ms = smin.query(l , r) - suf[r + 1];
        auto &v = posPref[mp + pref[l - 1]];
        int i = *lower_bound(v.begin() , v.end() , l);
        auto &u = posSuf[ms + suf[r + 1]];
        int j = *prev(upper_bound(u.begin() , u.end() , r));
        if(i < j)
            ans+=abs(mp) * (mp < 0) + abs(ms) * (ms < 0);
        else
            ans+=max((mp < 0) * abs(mp) , (ms < 0) * abs(ms));
        cout<<ans<<nl;
    }
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18