Submission #733328

#	Time	Username	Problem	Language	Result	Execution time	Memory
733328		bgnbvnbv	Election (BOI18_election)	C++14	100 / 100	1061 ms	69252 KiB

election

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,q;
string s;
vector<pli>t[maxN];
ll pre[maxN],bit[maxN],suff[maxN];
void upd(ll i,ll j)
{
    while(i<=n)
    {
        bit[i]+=j;
        i+=(i&(-i));
    }
}
ll gt(ll i)
{
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=(i&(-i));
    }
    return ans;
}
ll lazy[maxN*4]={0},st[4*maxN]={0};
void down(ll id)
{
    ll &x=lazy[id];
    st[id*2]+=x;
    st[id*2+1]+=x;
    lazy[id*2]+=x;
    lazy[id*2+1]+=x;
    x=0;
}
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=n+1)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]+=val;
        lazy[id]+=val;
        return;
    }
    ll mid=l+r>>1;
    down(id);
    update(i,j,val,id*2,l,mid);
    update(i,j,val,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n+1)
{
    if(j<l||r<i) return inf;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    down(id);
    return min(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
ll ans[maxN];
void solve()
{
    cin >> n ;
    cin >> s;
    s=' '+s;
    cin >> q;
    for(int i=1;i<=q;i++)
    {
        ll l,r;
        cin >> l >> r;
        t[l].pb({r,i});
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='C') pre[i]=pre[i-1]+1;
        else pre[i]=pre[i-1]-1;
    }
    update(n+1,n+1,0);
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='C') suff[i]=suff[i+1]+1;
        else suff[i]=suff[i+1]-1;
        update(i,i,suff[i]);
    }
    deque<int>dq;
    for(int i=n;i>=0;i--)
    {
        while(!dq.empty()&&pre[i]<=pre[dq.back()])
        {
            update(1,dq.back(),-1);
            upd(dq.back(),-1);
            dq.pop_back();
        }
        for(auto rr:t[i+1])
        {
            ll r=rr.fi;
            ll id=rr.se;
            ans[id]=gt(r);
            ll mn=get(i+1,r);
            ans[id]+=max(0ll,get(r+1,r+1)-mn);
        }
        if(i==0) break;
        dq.push_back(i);
        update(1,i,1);
        upd(i,1);
    }
    for(int i=1;i<=q;i++) cout << ans[i]<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

election.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
election.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     ll mid=l+r>>1;
      |            ~^~
election.cpp: In function 'll get(ll, ll, ll, ll, ll)':
election.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     ll mid=l+r>>1;
      |            ~^~

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