제출 #1039440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039440		vjudge1	Election (BOI18_election)	C++17	0 / 100	2 ms	6492 KiB

election

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 5e5+7;
struct segment_tree
{
    ll st[mxn<<2];
    void update(ll id, ll l, ll r, ll u, ll x)
    {
        if (r < u || u < l) return;
        if (l == r)
        {
            st[id] = (st[id]+x);
            return;
        }
        ll m = (r+l)>>1;
        update(id<<1,l,m,u,x); update(id<<1|1,m+1,r,u,x);
        st[id] = min(st[id<<1],st[id<<1|1]);
    }
    ll get(ll id, ll l, ll r, ll u, ll v)
    {
        if (r < u || v < l) return 1e18;
        if (u <= l && r <= v) return st[id];
        ll m = (r+l)>>1;
        return min(get(id<<1,l,m,u,v),get(id<<1|1,m+1,r,u,v));
    }
} st1, st2;
ll dpf[mxn], dpb[mxn], n, q;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n;
    string s; cin >> s;
    for (ll i = 1; i <= n; i++) 
    {
        dpf[i] = (s[i-1] == 'C' ? 1 : -1);
        dpf[i] += dpf[i-1];
        st1.update(1,1,n,i,dpf[i]);
    }
    for (ll i = n; i >= 1; i--)
    {
        dpb[i] = (s[i-1] == 'C' ? 1 : -1);
        dpb[i] += dpb[i+1];
        st2.update(1,1,n,i,dpb[i]);
    }
    cin >> q;
    while (q--)
    {
        ll l, r; cin >> l >> r;
        ll opt_l = st1.get(1,1,n,l,r)-dpf[l-1], opt_r = st2.get(1,1,n,l,r)-dpb[r+1];
        ll opt = min(opt_l,opt_r);
        if (opt >= 0) cout << 0 << '\n';
        else cout << -opt << '\n';
    }
}

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