Submission #546157

#	Time	Username	Problem	Language	Result	Execution time	Memory
546157		leaked	Fish 2 (JOI22_fish2)	C++14	100 / 100	1510 ms	60768 KiB

fish2

#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
const ll inf=1e18;
struct node{
    vec<array<ll,3>> pref,suf;
    ///their value, whom not exceed,cnt
    ll s;
    node(){
        s=0;
    }
};
int a[N];
node t[4*N];
node mg(node a,node b){
    node c;
    c.s=a.s+b.s;

    c.suf=b.suf;
    c.suf.pop_back();
    c.pref=a.pref;
    c.pref.pop_back();

    /// deleted fulls

    int j=0,k=0;
    int ok=0;
    vec<int> cnt1(sz(b.pref),0);
    vec<int> cnt2(sz(a.suf),0);
    for(int i=0;i<sz(b.pref);i++){
        umax(k,i);
        ok=1;
        while(ok){
            ok=0;
            if(k<sz(b.pref) && (a.suf[j][0]+b.pref[k][0])>=b.pref[k][1]) ++k,ok=1;
            if(j<sz(a.suf) && (a.suf[j][0]+b.pref[k][0])>=a.suf[j][1]) ++j,ok=1;
        }
//        cout<<"WOW "<<j<<' '<<k<<' '<<sz(b.pref)<<' '<<sz(a.suf)<<endl;
        if(k==sz(b.pref)-1) cnt2[j]+=b.pref[i][2];
        if(j==sz(a.suf)-1) cnt1[k]+=b.pref[i][2];
    }
    j=0;k=0;
    for(int i=0;i<sz(a.suf);i++){
        umax(j,i);
        ok=1;
        while(ok){
            ok=0;
            if(k<sz(b.pref) && (a.suf[j][0]+b.pref[k][0])>=b.pref[k][1]) ++k,ok=1;
            if(j<sz(a.suf) && (a.suf[j][0]+b.pref[k][0])>=a.suf[j][1]) ++j,ok=1;
        }
//        cout<<"WOW "<<j<<' '<<k<<' '<<sz(b.pref)<<' '<<sz(a.suf)<<endl;

        if(k==sz(b.pref)-1) cnt2[j]+=a.suf[i][2];
        if(j==sz(a.suf)-1) cnt1[k]+=a.suf[i][2];
    }

    for(int i=0;i<sz(a.suf);i++){
        if(cnt2[i]){
            assert(a.suf[i][1]>=(a.suf[i][0]+b.s));
        }
        if(a.suf[i][1]>(a.suf[i][0]+b.s))
            c.suf.pb({a.suf[i][0]+b.s,a.suf[i][1],cnt2[i]});
    }

    for(int i=0;i<sz(b.pref);i++){
        if(cnt1[i]){
            assert(b.pref[i][1]>=(b.pref[i][0]+a.s));
        }
        if(b.pref[i][1]>(b.pref[i][0]+a.s))
            c.pref.pb({b.pref[i][0]+a.s,b.pref[i][1],cnt1[i]});
    }
    return c;
}
void build(int v,int tl,int tr){
    if(tl==tr){
        int x=a[tl];
        t[v].pref.clear();t[v].suf.clear();
        t[v].s=x;
        t[v].pref.pb({0,x,0});
        t[v].suf.pb({0,x,0});
        t[v].pref.pb({x,inf,1});
        t[v].suf.pb({x,inf,1});
    }
    else{
        int tm=(tl+tr)>>1;
        build(2*v,tl,tm);build(2*v+1,tm+1,tr);
//        cout<<"ME "<<tl<<' '<<tr<<endl;
        t[v]=mg(t[2*v],t[2*v+1]);
    }
}
void upd(int i,int x,int v,int tl,int tr){
    if(tl==tr){
        t[v].pref.clear();t[v].suf.clear();
        t[v].s=x;
        t[v].pref.pb({0,x,0});
        t[v].suf.pb({0,x,0});
        t[v].pref.pb({x,inf,1});
        t[v].suf.pb({x,inf,1});
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=i)
        upd(i,x,2*v,tl,tm);
    else
        upd(i,x,2*v+1,tm+1,tr);
    t[v]=mg(t[2*v],t[2*v+1]);
}
node emp;
node get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r)
        return t[v];
    if(tl>r||tr<l)
        return emp;
    int tm=(tl+tr)>>1;
    return mg(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
signed main(){
    fast_prep;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    build(1,0,n-1);
    emp.pref.pb({0,inf,0});
    emp.suf.pb({0,inf,0});
//    return 0;
    int q;
    cin>>q;
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int i,x;
            cin>>i>>x;
            --i;
            upd(i,x,1,0,n-1);
        }
        else{
            int l,r;
            cin>>l>>r;--l;--r;
            node ans=get(l,r,1,0,n-1);
            assert(ans.suf.back()[1]==inf);
            cout<<ans.suf.back()[2]<<'\n';
        }
    }
    return 0;
}
/*

*/

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