Submission #939642

#	Time	Username	Problem	Language	Result	Execution time	Memory
939642		andrei_boaca	Fish 2 (JOI22_fish2)	C++17	60 / 100	1831 ms	34888 KiB

fish2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e17;
typedef pair<int,int> pii;
ll n,v[100005],q,s[100005],mars[100005];
int solve(int l,int r)
{
    s[l-1]=0;
    mars[l-1]=0;
    for(int i=l;i<=r;i++)
    {
        s[i]=s[i-1]+v[i];
        mars[i]=0;
    }
    stack<int> coada;
    for(int i=l;i<=r;i++)
    {
        while(!coada.empty()&&v[coada.top()]<v[i])
            coada.pop();
        int st=l-1;
        if(!coada.empty())
            st=coada.top();
        if(s[i-1]-s[st]<v[i])
        {
            mars[st+1]++;
            mars[i]--;
        }
        coada.push(i);
    }
    while(!coada.empty())
        coada.pop();
    for(int i=r;i>=l;i--)
    {
        while(!coada.empty()&&v[coada.top()]<v[i])
            coada.pop();
        int dr=r+1;
        if(!coada.empty())
            dr=coada.top();
        if(s[dr-1]-s[i]<v[i])
        {
            mars[i+1]++;
            mars[dr]--;
        }
        coada.push(i);
    }
    int ans=0;
    for(int i=l;i<=r;i++)
    {
        mars[i]+=mars[i-1];
        if(mars[i]==0)
            ans++;
    }
    return ans;
}
ll aib[100005];
ll lsb(ll x)
{
    return x&(-x);
}
void aibupd(ll poz,ll val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
ll suma(ll poz)
{
    ll rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
struct date
{
    ll minim,cnt;
} arb[4*100005];
ll toprop[4*100005];
struct prostie
{
    ll maxim,poz;
} arbdir[2][4*100005]; /// 0 -> st, 1 -> dr
ll topropdir[2][4*100005];
date combine(date a, date b)
{
    if(a.minim<b.minim)
        return a;
    if(a.minim>b.minim)
        return b;
    a.cnt+=b.cnt;
    return a;
}
void prop(ll nod)
{
    ll val=toprop[nod];
    arb[nod*2].minim+=val;
    arb[nod*2+1].minim+=val;
    toprop[nod*2]+=val;
    toprop[nod*2+1]+=val;
}
void update(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
    if(st!=dr)
        prop(nod);
    toprop[nod]=0;
    if(st>=a&&dr<=b)
    {
        arb[nod].minim+=val;
        toprop[nod]+=val;
        return;
    }
    ll mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
    arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
prostie combinedir(prostie a, prostie b)
{
    if(a.maxim>=b.maxim)
        return a;
    return b;
}
void propdir(ll ind,ll nod)
{
    ll val=topropdir[ind][nod];
    arbdir[ind][nod*2].maxim+=val;
    arbdir[ind][nod*2+1].maxim+=val;
    topropdir[ind][nod*2]+=val;
    topropdir[ind][nod*2+1]+=val;
}
void updatedir(ll ind,ll nod,ll st,ll dr,ll a,ll b,ll val)
{
    if(st!=dr)
        propdir(ind,nod);
    topropdir[ind][nod]=0;
    if(st>=a&&dr<=b)
    {
        arbdir[ind][nod].maxim+=val;
        topropdir[ind][nod]+=val;
        return;
    }
    ll mij=(st+dr)/2;
    if(a<=mij)
        updatedir(ind,nod*2,st,mij,a,b,val);
    if(b>mij)
        updatedir(ind,nod*2+1,mij+1,dr,a,b,val);
    arbdir[ind][nod]=combinedir(arbdir[ind][nod*2],arbdir[ind][nod*2+1]);
}
prostie querydir(ll ind,ll nod,ll st,ll dr,ll a,ll b)
{
    if(st!=dr)
        propdir(ind,nod);
    topropdir[ind][nod]=0;
    if(st>=a&&dr<=b)
        return arbdir[ind][nod];
    prostie rez={-2LL*INF,0};
    ll mij=(st+dr)/2;
    if(a<=mij)
        rez=combinedir(rez,querydir(ind,nod*2,st,mij,a,b));
    if(b>mij)
        rez=combinedir(rez,querydir(ind,nod*2+1,mij+1,dr,a,b));
    return rez;
}
void build(int nod,int st,int dr)
{
    arb[nod].cnt=(dr-st+1);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void builddir(int nod,int st,int dr)
{
    arbdir[0][nod]=arbdir[1][nod]={0,st};
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    builddir(nod*2,st,mij);
    builddir(nod*2+1,mij+1,dr);
}
set<pii> setik;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    cin>>q;
    if(q<=1000)
    {
        while(q--)
        {
            int tip;
            cin>>tip;
            if(tip==1)
            {
                int poz,val;
                cin>>poz>>val;
                v[poz]=val;
            }
            else
            {
                int l,r;
                cin>>l>>r;
                cout<<solve(l,r)<<'\n';
            }
        }
        return 0;
    }
    v[0]=INF;
    v[n+1]=INF;
    build(1,1,n);
    builddir(1,1,n);
    for(int i=1;i<=n;i++)
        aibupd(i,v[i]);
    stack<int> coada;
    for(int i=1;i<=n;i++)
    {
        while(!coada.empty()&&v[coada.top()]<v[i])
            coada.pop();
        int st=0;
        if(!coada.empty())
            st=coada.top();
        if(suma(i-1)-suma(st)<v[i])
        {
            /*mars[st+1]++;
            mars[i]--;*/
            if(st+1<=i-1)
                setik.insert({st+1,i-1});
        }
        coada.push(i);
    }
    while(!coada.empty())
        coada.pop();
    for(int i=n;i>=1;i--)
    {
        while(!coada.empty()&&v[coada.top()]<v[i])
            coada.pop();
        int dr=n+1;
        if(!coada.empty())
            dr=coada.top();
        if(suma(dr-1)-suma(i)<v[i])
        {
            /*mars[i+1]++;
            mars[dr]--;*/
            if(i+1<=dr-1)
                setik.insert({i+1,dr-1});
        }
        coada.push(i);
    }
    while(!coada.empty())
        coada.pop();
    for(int i=1;i<=n;i++)
    {
        updatedir(0,1,1,n,i,i,v[i]);
        updatedir(1,1,1,n,i,i,v[i]);
        if(i+1<=n)
            updatedir(0,1,1,n,i+1,n,-v[i]);
        if(i-1>=1)
            updatedir(1,1,1,n,1,i-1,-v[i]);
    }
    for(auto p:setik)
        update(1,1,n,p.first,p.second,+1);
    while(q--)
    {
        ll tip;
        cin>>tip;
        if(tip==1)
        {
            ll i,val;
            cin>>i>>val;
            updatedir(0,1,1,n,i,i,-v[i]);
            updatedir(1,1,1,n,i,i,-v[i]);
            if(i+1<=n)
                updatedir(0,1,1,n,i+1,n,v[i]);
            if(i-1>=1)
                updatedir(1,1,1,n,1,i-1,v[i]);
            aibupd(i,-v[i]);
            v[i]=val;
            updatedir(0,1,1,n,i,i,v[i]);
            updatedir(1,1,1,n,i,i,v[i]);
            if(i+1<=n)
                updatedir(0,1,1,n,i+1,n,-v[i]);
            if(i-1>=1)
                updatedir(1,1,1,n,1,i-1,-v[i]);
            aibupd(i,v[i]);
            vector<int> lft,rgt;
            if(i>1)
            {
                ll S=suma(n)-suma(i-1);
                while(true)
                {
                    prostie a=querydir(1,1,1,n,1,i-1);
                    a.maxim+=S;
                    if(a.maxim<0)
                        break;
                    lft.push_back(a.poz);
                    updatedir(1,1,1,n,a.poz,a.poz,-INF);
                }
                for(ll p:lft)
                    updatedir(1,1,1,n,p,p,+INF);
            }
            if(i+1<=n)
            {
                ll S=suma(i);
                while(true)
                {
                    prostie a=querydir(0,1,1,n,i+1,n);
                    a.maxim+=S;
                    if(a.maxim<0)
                        break;
                    rgt.push_back(a.poz);
                    updatedir(0,1,1,n,a.poz,a.poz,-INF);
                }
                for(ll p:rgt)
                    updatedir(0,1,1,n,p,p,+INF);
            }
            lft.push_back(i);
            rgt.push_back(i);
            lft.push_back(0);
            rgt.push_back(n+1);
            for(ll l:lft)
                for(ll r:rgt)
                {
                    ll st=l+1;
                    ll dr=r-1;
                    if(st<=dr)
                    {
                        if(suma(dr)-suma(st-1)<min(v[l],v[r]))
                        {
                            if(setik.find({st,dr})==setik.end())
                            {
                                setik.insert({st,dr});
                                update(1,1,n,st,dr,+1);
                            }
                        }
                        else
                        {
                            if(setik.find({st,dr})!=setik.end())
                            {
                                setik.erase({st,dr});
                                update(1,1,n,st,dr,-1);
                            }
                        }
                    }
                }
        }
        else
        {
            int l,r;
            cin>>l>>r;
            cout<<arb[1].cnt<<'\n';
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 17