oj.uz

Submission #733328

# Submission time Handle Problem Language Result Execution time Memory
733328 2023-04-30T13:14:04 Z bgnbvnbv Election (BOI18_election) C++14
100 / 100
 1061 ms 69252 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 9 ms 12220 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 9 ms 12220 KB Output is correct
6 Correct 140 ms 21524 KB Output is correct
7 Correct 105 ms 21452 KB Output is correct
8 Correct 110 ms 21212 KB Output is correct
9 Correct 121 ms 21452 KB Output is correct
10 Correct 114 ms 21320 KB Output is correct
11 Correct 114 ms 21672 KB Output is correct
12 Correct 127 ms 21596 KB Output is correct
13 Correct 122 ms 21704 KB Output is correct
14 Correct 111 ms 21632 KB Output is correct
15 Correct 147 ms 21528 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 9 ms 12220 KB Output is correct
6 Correct 140 ms 21524 KB Output is correct
7 Correct 105 ms 21452 KB Output is correct
8 Correct 110 ms 21212 KB Output is correct
9 Correct 121 ms 21452 KB Output is correct
10 Correct 114 ms 21320 KB Output is correct
11 Correct 114 ms 21672 KB Output is correct
12 Correct 127 ms 21596 KB Output is correct
13 Correct 122 ms 21704 KB Output is correct
14 Correct 111 ms 21632 KB Output is correct
15 Correct 147 ms 21528 KB Output is correct
16 Correct 1061 ms 67636 KB Output is correct
17 Correct 900 ms 66756 KB Output is correct
18 Correct 955 ms 65788 KB Output is correct
19 Correct 930 ms 66684 KB Output is correct
20 Correct 1028 ms 66680 KB Output is correct
21 Correct 1008 ms 68980 KB Output is correct
22 Correct 1014 ms 68456 KB Output is correct
23 Correct 1025 ms 69252 KB Output is correct
24 Correct 1040 ms 68636 KB Output is correct
25 Correct 992 ms 67748 KB Output is correct